Для подстрок и нечетких совпадений алгоритм расстояния Левенштейна работал для меня довольно хорошо. Хотя я признаю, что он не так совершенен, как отраслевые реализации автозаполнения / предложения. Я думаю, что и Google, и Intellisense от Microsoft делают лучшую работу, потому что они усовершенствовали этот базовый алгоритм, чтобы взвесить тот тип операций редактирования, который требуется для соответствия разнородным строкам. Например. транспонирование двух символов должно, вероятно, считаться только 1 операцией, а не 2 (вставка и удаление).
Но даже в этом случае я нахожу это достаточно близким. Вот его реализация в C # ...
// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
// it more like Google's autocomplete/suggest. It returns the number of operations
// (insert/delete/substitute) required to change one string into another, with the
// expectation that userTyped is only a partial version of fullEntry.
// Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities
return 0; // at this point, because the user hasn't typed anything.
var inx = fullEntry.IndexOf(userTyped[0]);
if (inx < 0) // If the 1st character doesn't exist anywhere in the entry, it's not
return Int32.MaxValue; // a possible match.
var lastInx = inx;
var lastMatchCount = 0;
TryAgain:
// Is there a better starting point?
var len = fullEntry.Length - inx;
var matchCount = 1;
var k = 1;
for (; k < len; k++)
{
if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
{
if (matchCount > lastMatchCount)
{
lastMatchCount = matchCount;
lastInx = inx;
}
inx = fullEntry.IndexOf(userTyped[0], inx + 1);
matchCount = 0;
if (inx > 0)
goto TryAgain;
else
break;
}
else
matchCount++;
}
if (k == len && matchCount > lastMatchCount)
lastInx = inx;
if (lastInx > 0)
fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values
// The start of the Levenshtein Distance algorithem.
var m = userTyped.Length;
var n = Math.Min(m, fullEntry.Length);
int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations.
for (var i = 0; i <= m; i++)
d[i, 0] = i; // the distance of any first string to an empty second string
for (var j = 0; j <= n; j++)
d[0, j] = j; // the distance of any second string to an empty first string
for (var j = 1; j <= n; j++)
for (var i = 1; i <= m; i++)
if (userTyped[i - 1] == fullEntry[j - 1])
d[i, j] = d[i - 1, j - 1]; // no operation required
else
d[i, j] = Math.Min
(
d[i - 1, j] + 1, // a deletion
Math.Min(
d[i, j - 1] + 1, // an insertion
d[i - 1, j - 1] + 1 // a substitution
)
);
return d[m, n];
}