В продолжении соседней темы

Вроде расстояние Л. является стандартом но для неточного поиска както оно плохо подходит
потому что если у нас есть строки

xyz
abc123456

и мы ищем по ним запросом

abc

то Л. даст меньшую длину для xyz чем для abc123456
хотя abc123456 содержит запрос abc и выглядит более подходящим

т.е. в идеале нужен метрический алгорим который будет искать подстроку, которая ближайшая к запросу

ЖПТ мне сходу написал просто Левенштейна который двигает ту строку, что короче, по той, которая длиннее и ищет минимальное дистанцию,

public static int SubstringAwareLevenshtein(string a, string b)
{
int minDist = int.MaxValue;

// Сравниваем a со всеми подстроками b
for (int i = 0; i <= b.Length — a.Length; i++)
{
string sub = b.Substring(i, a.Length);
int dist = ComputeLevenshteinDistance(a, sub);
if (dist < minDist)
minDist = dist;
}

// Сравниваем b со всеми подстроками a
for (int i = 0; i <= a.Length — b.Length; i++)
{
string sub = a.Substring(i, b.Length);
int dist = ComputeLevenshteinDistance(b, sub);
if (dist < minDist)
minDist = dist;
}

return minDist;
}

это уже лучше, но не факт что он найдет таким образом лучшее совпадение, а самое хреновое что Л итак медленный а тут еще в M-N раз больше его вызывать нада

мне пришла другая но незаконченная идея:
суть ее в том что мы сначала находим подстроку которая содержит все символы запроса, а потом левенштейним ее с запросом

public int ComputeDistance(string p, string t)
{
if(p.Length > t.Length)
{
var x = p;
p = t;
t = x;
}

var d = 0;

var min = int.MaxValue;
var max = int.MinValue;

for(int i = 0; i < p.Length; i++)
{
var j = t.IndexOf(p[i]);

if(j != -1)
{
if(j < min)
min = j;

if(j > max)
max = j;
}
else
{

// непонятно что тут делать
}
}


return ComputeLevenshteinDistance(t.Substing(min, max — min), p);
}

но если символ не найден, то хрен его знает что делать,
всякие тупые "+ чтото" не работают потому что с ними функция не получается метрической

В продолжении соседней темы

Вроде расстояние Л. является стандартом но для неточного поиска както оно плохо подходит
потому что если у нас есть строки

xyz
abc123456

и мы ищем по ним запросом

abc

то Л. даст меньшую длину для xyz чем для abc123456
хотя abc123456 содержит запрос abc и выглядит более подходящей

т.е. в идеале нужен метрический алгорим который будет искать подстроку, которая ближайшая к запросу

ЖПТ мне сходу написал просто Левенштейна который двигает ту строку, что короче, по той, которая длиннее и ищет минимальное дистанцию,

public static int SubstringAwareLevenshtein(string a, string b)
{
int minDist = int.MaxValue;

// Сравниваем a со всеми подстроками b
for (int i = 0; i <= b.Length — a.Length; i++)
{
string sub = b.Substring(i, a.Length);
int dist = ComputeLevenshteinDistance(a, sub);
if (dist < minDist)
minDist = dist;
}

// Сравниваем b со всеми подстроками a
for (int i = 0; i <= a.Length — b.Length; i++)
{
string sub = a.Substring(i, b.Length);
int dist = ComputeLevenshteinDistance(b, sub);
if (dist < minDist)
minDist = dist;
}

return minDist;
}

это уже лучше, но не факт что он найдет таким образом лучшее совпадение, а самое хреновое что Л итак медленный а тут еще в M-N раз больше его вызывать нада

мне пришла другая но незаконченная идея:
суть ее в том что мы сначала находим подстроку которая содержит все символы запроса, а потом левенштейним ее с запросом

public int ComputeDistance(string p, string t)
{
if(p.Length > t.Length)
{
var x = p;
p = t;
t = x;
}

var d = 0;

var min = int.MaxValue;
var max = int.MinValue;

for(int i = 0; i < p.Length; i++)
{
var j = t.IndexOf(p[i]);

if(j != -1)
{
if(j < min)
min = j;

if(j > max)
max = j;
}
else
{

// непонятно что тут делать
}
}


return ComputeLevenshteinDistance(t.Substing(min, max — min), p);
}

но если символ не найден, то хрен его знает что делать,
всякие тупые "+ чтото" не работают потому что с ними функция не получается метрической