Есть два текста одного и того же документа. Требуется найти совпадающие или почти совпадающие фрагменты. Ну то есть например в одном тексте есть шапка и комментарии. А в другом нет. Но нужно определить и желательно быстро те фрагменты двух текстов, которые одинаковы.
Особенно ценно было бы находить нечёткие совпадения. Например, один текст был получен в результате распознавания образа и местами он довольно кривой.
Пожалуйста, подскажите направление. Какие алгоритмы можно применить, что почитать?
Ну начать с применения расстояния Левенштейна, Хэмминга и других подобных методов. Если это действительно два почти одингаковых текста, то может неплохо подойти.
Но сравнивать лучше не тексты целиком, а кусками: разделами, абзацами, предложениями...
shurshur, ну вот я думал уже в этом направлении. Но как мне, например, сделать своего рода «нечёткий хэш» предложения? Так чтобы если, скажем в одном из текстов слово не распозналось толком, то соответствие предложений всё равно было найдено...
Так-то есть https://ru.wikipedia.org/wiki/Diff
Есть Git, в котором тоже какой-то алгоритм сравнения текстов, а поскольку open source, то никто не запрещает взять исходники и расковырять.
posters, согласен, интересная, но сложная. За 5 минут тут чего-то насоветовать нельзя, требуется погружаться в проблему с головой.
Спасибо всем ответившим. Дифф, конечно, идеально, но там диффер сдохнет, если сравнивать даже пословно, тексты довольно большие. А разделение по параграфам и строкам может быть разным, так что их сравнивать тоже не вариант.
Поэтому я пришёл к решению, когда я нормализую текст, удаляя знаки препинания и прочие незначащие символы, а затем итеративно сворачиваю в хеши сначала слова, а потом и сочетания слов-хешей. И сравниваю на каждом уровне, находя различающиеся фрагменты и уточняя сравнение. В итоге можно и до символов дойти, если надо. Но мне достаточно по словам сравнить.
Средний
