106 lines
3.1 KiB
C#
106 lines
3.1 KiB
C#
using System;
|
|
using System.Linq;
|
|
using System.Collections.Generic;
|
|
using System.Security.Cryptography;
|
|
using System.Web;
|
|
|
|
namespace MileageTraker.Web.Utility
|
|
{
|
|
public static class Algorithms
|
|
{
|
|
public static double Similarity<T>(IEnumerable<T> x, IEnumerable<T> y)
|
|
where T : IEquatable<T>
|
|
{
|
|
return 1.0 - (double)EditDistance(x, y) / Math.Max(x.Count(), y.Count());
|
|
}
|
|
|
|
/// <SUMMARY>Computes the Levenshtein Edit Distance between two enumerables.</SUMMARY>
|
|
/// <TYPEPARAM name="T">The type of the items in the enumerables.</TYPEPARAM>
|
|
/// <PARAM name="x">The first enumerable.</PARAM>
|
|
/// <PARAM name="y">The second enumerable.</PARAM>
|
|
/// <RETURNS>The edit distance.</RETURNS>
|
|
/// <remarks>http://blogs.msdn.com/b/toub/archive/2006/05/05/590814.aspx</remarks>
|
|
public static int EditDistance<T>(IEnumerable<T> x, IEnumerable<T> y)
|
|
where T : IEquatable<T>
|
|
{
|
|
// Validate parameters
|
|
if (x == null) throw new ArgumentNullException("x");
|
|
if (y == null) throw new ArgumentNullException("y");
|
|
|
|
// Convert the parameters into IList instances
|
|
// in order to obtain indexing capabilities
|
|
var first = x as IList<T> ?? new List<T>(x);
|
|
var second = y as IList<T> ?? new List<T>(y);
|
|
|
|
// Get the length of both. If either is 0, return
|
|
// the length of the other, since that number of insertions
|
|
// would be required.
|
|
int n = first.Count, m = second.Count;
|
|
if (n == 0) return m;
|
|
if (m == 0) return n;
|
|
|
|
// Rather than maintain an entire matrix (which would require O(n*m) space),
|
|
// just store the current row and the next row, each of which has a length m+1,
|
|
// so just O(m) space. Initialize the current row.
|
|
int curRow = 0, nextRow = 1;
|
|
var rows = new[] {new int[m + 1], new int[m + 1]};
|
|
for (var j = 0; j <= m; ++j) rows[curRow][j] = j;
|
|
|
|
// For each virtual row (since we only have physical storage for two)
|
|
for (var i = 1; i <= n; ++i)
|
|
{
|
|
// Fill in the values in the row
|
|
rows[nextRow][0] = i;
|
|
for (var j = 1; j <= m; ++j)
|
|
{
|
|
int dist1 = rows[curRow][j] + 1;
|
|
int dist2 = rows[nextRow][j - 1] + 1;
|
|
int dist3 = rows[curRow][j - 1] +
|
|
(first[i - 1].Equals(second[j - 1]) ? 0 : 1);
|
|
|
|
rows[nextRow][j] = Math.Min(dist1, Math.Min(dist2, dist3));
|
|
}
|
|
|
|
// Swap the current and next rows
|
|
if (curRow == 0)
|
|
{
|
|
curRow = 1;
|
|
nextRow = 0;
|
|
}
|
|
else
|
|
{
|
|
curRow = 0;
|
|
nextRow = 1;
|
|
}
|
|
}
|
|
|
|
// Return the computed edit distance
|
|
return rows[curRow][m];
|
|
}
|
|
|
|
public static bool IsChronological(DateTime existingDate, int existingNumber, DateTime date, int number)
|
|
{
|
|
return existingDate == date
|
|
|| existingNumber == number
|
|
|| existingDate < date && existingNumber < number
|
|
|| existingDate > date && existingNumber > number;
|
|
}
|
|
|
|
private const int TokenSizeInBytes = 16;
|
|
|
|
public static string GenerateToken()
|
|
{
|
|
using (var prng = new RNGCryptoServiceProvider())
|
|
{
|
|
return GenerateToken(prng);
|
|
}
|
|
}
|
|
|
|
private static string GenerateToken(RandomNumberGenerator generator)
|
|
{
|
|
var tokenBytes = new byte[TokenSizeInBytes];
|
|
generator.GetBytes(tokenBytes);
|
|
return HttpServerUtility.UrlTokenEncode(tokenBytes);
|
|
}
|
|
}
|
|
} |