Стат сумма, хеширование, контрольная сумма для сравнения двух текстовых строк.

#алгоритм #хеширование

Есть следующая задача, допустим, есть текстовые строки одинаковой длины. 
Допустим, используются только буквы ABCD. Нужно ввести метрику, способ подсчёта контрольной
суммы и тп. (не знаю как более точно обозвать), чтобы можно было сравнивать строки
между собой по их контрольным суммам. 
То есть:
ABCDABCD и ABCDABCC - очень близкие строки с одной заменой. (1)
ABCDABCD и ABCDDABC - тоже очень близкие строки с одной вставкой "D".
Насколько я представляю, нужно иметь на выходе некоторую постоянную и вариабельную
часть. 
Чтобы в первом примере (1) SUM(ABCDABCD)='wtyy45t'.004 а SUM(ABCDABCC)='wtyy45t'.007
(цифры и буквы условны). 
И в тоже время:  SUM(ABCDABCD)='wtyy45t'.004 а SUM(DDACBADB)='yiejq07'.163
Чтобы можно было потом легко сравнивать похожие строки и откидывать совсем разные. 
Буду благодарен за любые ссылки на алгоритмы, предложения, советы. Спасибо.
UPD
Основной момент - различных строк будет несколько сотен тысяч. Нет возможности их
сравнивать между собой по сложным критериям. Хочется группировать их в кластеры по
общей постоянной части контрольной суммы.    

Ответы

Ответ 1

Как уже отметил margosh, вам следует уточнить требуемое понятие похожести, алгоритма
is_strings_similar_like_i_want нет, и подобной функции не найдете даже в пхп. Пока
можно рекомендовать полистать Энциклопедический словарь расстояний, в главе 11 приведены
все известные метрики на множествах строк.


Ответ 2

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

Выяснить длину строки и предел количества символов, которые могут быть отличны (судя
по Вашим пояснениям - 30%)
Поисмвольно вычесть одну строку из другой, если количество "ненулевых" символов в
результате превышает предел и данные символы располагаются вразброс - в строке были
замены, стока по количеству замен отбрасывается, если же ненулевые символы идут строем
- на лицо сдвиг или делеция, и необходимо сохранить позицию первого отличного символа
и продолжить анализ. Соответственно при количестве "ненулевых" символов в результате
меньше предела - строки похожи.
Далее, в случае сдвигов и делеций должен быть цикл, ограниченный пределом количества
отличных символов (Nlim), в котором проверяются : сопадение первого несовпавшего символа
(позиция m) с одним из символов последующих позиций базовой строки (но не более m +
Nlim). В случае совпадения на некоторой позиции r, проверяется совпадение последующих
символов строки m+i с символами базовой строки m+r+i,теоретически, можно вынести эти
куски в отдельные строки и воспользоваться пунктом 2.
Для вставки сверяем символы строки в позиции от m до m+Nlim с символом базовой строки
в позиции m.


Пример : 
вставка : ABCDABCD и ABCDCDABСD, рез. - 00001111, m=4,r=6, позиции 4-7 базовой и
6-9 совпадают
Как быть со строками разной длины - Вам, как автору темы, виднее.

PS: Эти наброски, безусловно, не претендуют на полноту, простоту и быстроту реализации.


Ответ 3

Учитывая то что ваши строки имеют одинаковую длину, то я бы ввел метрику редактирования,
то есть сколько замен букв требуется, для получения одного слова из другого.
ABCDABCD и ABCDABCC - очень близкие строки с одной заменой. (1)
Алгоритм вычисления данной метрики O(LENGTH(str)).


Ответ 4

Если число используемых символов ограничено какой-то разумной величиной N (ну скажем
меньше 16), то лучший способ это трансляция строк в некое длинное целое используя в
качестве метрики позиционный способ записи N-тиричной системе счисления. Скажем ваш
пример с четырьмя символами ABCD - легко ложится под 4-х тиричную систему счисления.
Строка:

ABCDABCD -> 01230123
ABCDABCC -> 01230122

Ну а дальше сравнение целых это уже просто.


Ответ 5

Вопрос, на самом деле, очень хороший! И пока, решение @Barmaleyя самое лучшее. У
меня нет лучшей идеи по этому поводу, разве что только XORить строки с определенной
"солью" и опять же снова вычислять номер каждого символа. Это будет надежнее, но гораздо
дольше, чем "неХОРеные" строки. 

А вообще советую вам смотреть в сторону PHP-функции similar_text() . Эта функция
вычисляет степень похожести двух строк. Посмотрите её сорцы( они, как мне известно
на C++ ), да поймете, как она работает, напишете свою.


Ответ 6

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


Ответ 7

Я думаю, здесь поможет преобразование Барроуза-Уилера.