Нечёткий алгоритм определения совпадения строк

[Edgar Akhmadeev]

Понадобился такой алгоритм, чтобы определять, есть ли неполное, но сильное совпадение двух строк. К примеру, "Aeternity line" и "Æternity".

Я-то написал алгоритм, ищущий брутфорсом, перебором. Возвращает в данном примере 7/14=0.5

Хотелось бы знать, есть ли нормальный, умный и быстрый алгоритм в какой-нибудь библиотеке. Или рассчитывать что-то вроде хеш-функции. Только не надо, чтобы одинаковое количество одинаковых букв, но в разных местах, давало ложный результат.

Если интересно, вот мой тупой алгоритм

#property copyright "(c)2024 Edgar Akhmadeev"
#property link      "https://www.mql5.com/en/users/dali"
#property version   "1.00"
// 2024.01.31

// Коэффициент совпадения строк
double
StringCompareFuzzy(string s1, string s2) {
        int sSz, mSz, sz;
        string s, m;
        int size1 = StringLen(s1);
        int size2 = StringLen(s2);
        if (size1 > size2) {
                s = s1;
                m = s2;
                sSz = size1;
                mSz = size2;
                sz = size1;
        }
        else {
                s = s2;
                m = s1;
                sSz = size2;
                mSz = size1;
                sz = size2;
        }
        
        int len = 0;
        for (int sI = 0; sI < sSz; ++sI) {
                bool found = false;
                int mIdx = 0;
                int sIdx = 0;
                int mI;
                for (mI = 0; mI < mSz; ++mI) {
                        if (StringGetCharacter(m, mI) != StringGetCharacter(s, sI + sIdx++)) {
                                if (!found)
                                        sIdx = 0;
                                else {
                                        if (len < mI - mIdx)
                                                len = mI - mIdx;
                                        break;
                                }
                                        
                        }
                        else if (!found) {
                                found = true;
                                mIdx = mI;
                        }
                }
                
                if (found && len < mI - mIdx)
                        len = mI - mIdx;
        }
        
        return (double)len / sz;
}

[Sergey Gridnev]

https://habr.com/ru/articles/676858/

[Edgar Akhmadeev]

Sergey Gridnev #:
https://habr.com/ru/articles/676858/

Спасибо. Буду изучать. 

Вот никогда бы не нашёл в гугле. Для этого надо знать слова " расстояние Левенштейна" или  "редакционное расстояние" ))

[Valeriy Yastremskiy]

Sergey Gridnev #:
https://habr.com/ru/articles/676858/

Спасибо)))