Можно я присоединюсь к вопросу, расширив его до:
Имеется очень большое количество строк (в общем случае, с бинарными данными, конечно было бы лучше). Эти строки очень похожи! Размер строк варьируется в пределах от считанных байт до нескольких десятков килобайт.
лучшее что можно сказать про эти строки, — грубо говоря, это различные сообщения по некоторому количеству шаблонов (их количество тоже заранее неизвестное, но тоже большое, примерно количество сравнимое с log(n)). Нет возможности заранее получить эти шаблоны (источник данных независим), мало того, во времени шаблоны меняются, т.е. могут появляться новые и исчезать старые.
Задача, с некоторым приближением (речь не идет о максимальной эффективности), обнаруживать похожие сообщения, или в терминах описанной выше информации об этих строках — выявить шаблон для каждого сообщения. Уровень эффективности можно определить по размеру патча какого-либо diff-алгоритма (тот же bzdiff).
Если задачу решать нахрапом, то это для каждого следующего сообщения производить сравнение с каждым предыдущим (можно взять некоторое окно во времени), вычислять расстояние (размер diff патча) и брать наименьшее.
Дальше можно оптимизировать на основе предположения что если сообщение A находится на расстоянии от B и если C находится на примерно таком же раасстоянии от B, то расстояние между A и C будет примерно таким же, а значит если хранить матрицу расстояний между сообщениями (не для всех а только проверяемых) то расстояние для не проверенных пар можно вычислять из соседних 'соседних'. Можно даже пройтись по архиву и выявить коэффицент/погрешность, которая накапливается если использовать это вышеописанное предположение (A->B)&(C->B) = (A->C) многократно для A->D, A->E на основе таких же вычисленных B->D и B->E или даже D->E… в общем чтобы вместо трудоемкости N*M получить хотя бы N*log(M) где N — количество сообщений, M — размер окна, количество последних сравниваемых собщений (в этом случае их можно уже считать шаблонами).
Простой
