Альтернативная модель сходства символьных строк © С. В. Знаменский 1 © В. А. Дьяченко2 Институт программных систем имени А. К. Айламазяна РАН, 1 Переславль-Залесский 2 Ярославский государственный университет имени П. Г. Демидова, Ярославль svz@latex.pereslavl.ru dyachenko.vlad_76@mail.ru Аннотация. Выразительные примеры показывают, что нормализация меры сходства, равно как и замена её метрикой могут приводить к ошибкам кластеризации и ранжирования по сходству. Для задач, в которых сходство определяется выравниванием, описан аналог OCS длиннейшей общей подпоследовательности LCS (Longest Common Subsequence). Предлагаемая модель отвечает потреб- ностям базовых приложений, в которых совпадение подстрок более значимо, чем совпадение разре- женных подпоследовательностей той же длины. OCS обещает ускорить приближённый поиск, но точное вычисление за счёт более тонкой градации значений требует умеренных дополнительных ре- сурсов по сравнению с LCS. Общие диапазоны значений и базовые свойства упрощают миграцию работающих на LCS приложений. Ключевые слова: мера сходства, метрика близости, LCS, общая подпоследовательность, вы- равнивание последовательностей, кластеризация, ранжирование. An Alternative Model of the Strings Similarity © Sergej Znamenskii1 © Vladislav Dyachenko2 1 A. K. Ailamazyan Program Systems Institute of Russian academy of Science, Pereslavl-Zalessky 2 P. G. Demidov Yaroslavl State University, Yaroslavl svz@latex.pereslavl.ru dyachenko.vlad_76@mail.ru Abstract. Expressive examples show that either the normalization of the similarity measure or its replace- ment by metrics may lead to errors of clustering and ranking by similarity. For applications of alignment-based similarity, an analog OCS of the longest common subsequence (LCS) is described. A proposed model re- sponds the needs of the basic LCS applications in which the matching of substrings is more significant than the coincidence of sparse subsequences of the same length. OCS promises to speed up fuzzy search, but ac- curate calculation due to a finer gradation of values requires moderate additional resources compared to LCS. Common value ranges and basic properties make it easy to migrate applications running on LCS. Keywords: similarity measure, similarity metric, LCS, common subsequence, sequence alignment, clustering, ranking. Обработка информации различной природы, 1 Метрики близости и меры сходства представленной символьными строками, базируется Символьные строки над конечным алфавитом на численных оценках сходства, обеспечивающих используются для компьютерного представления возможности ранжирования по сходству, кластери- информации различной природы при поиске плаги- зации и нечёткого поиска и подробно описанных в ата, работе с версиями исходного кода программ, многочисленных публикациях. распознавании звуков и поиске мелодий, анализе Не только численные значения оценки сходства данных биоинформатики, грубой сортировке сырых символьных строк, но и основанные на них резуль- текстовых историко-географических данных и в таты ранжирования по сходству или кластеризации других прикладных задачах. существенно зависят от непростого выбора способа количественной оценки пары строк в основном сре- Труды XIX Международной конференции «Ана- ди двух групп: литика и управление данными в областях с ин- Метрики близости оценивают расстояние меж- тенсивным использованием данных» (DAMDID/ ду строками. Для строки и её подстроки – это обыч- RCDL’2017), Москва, Россия, 10–13 октября 2017 но разность длин. Формально удовлетворяют из- года 177 вестным аксиомам метрического пространства. алгоритм, основанный на метрике, ошибётся в этой Меры сходства оценивают размер общей ин- ситуации. Использование метрики близости в каче- формации либо мощность пересечения множеств стве меры сходства на таких данных порождает признаков. Для строки и её подстроки – это обычно ошибки в теоретических выводах и приложениях. длина подстроки. Неотрицательны и монотонны по Вывод 1. Метрику близости рискованно исполь- включению. Некоторые из них могут считаться ме- зовать для кластеризации (или ранжирования) по рами в смысле классической теории меры, осталь- сходству строк существенно различной длины: раз- ные (включая LCS) формализуются как нечёткие личия в длинах маскируют сходство. меры Шоке–Суджено на множестве признаков. Ча- 1.2 Ошибочное нормирование сходства сто называются метриками сходства, что порождает не всегда корректную ассоциацию с метрическим Хорошо известно, что метрику можно норми- пространством. ровать без потерь. Простая связь меры близости с метрикой сходства скрывает фундаментальные раз- Классический подход к построению меры сход- личия. Ошибки, связанные с нормированием, отчёт- ства символьных строк 𝑎𝑎 и 𝑏𝑏 состоит в вырав- ливо видны на строках 𝑢𝑢 = «USA», 𝑟𝑟 = «RUSSIA» и нивании строк выделением в каждой из них оди- 𝑟𝑟𝑓𝑓 = «RUSSIAN FEDERATION» и мере сходства наковых подпоследовательностей символов. LCS: ненормированный LCS вполне обоснованно Выбор длиннейшей из всех таких возможных позиционирует «RUSSIA» в два раза ближе к подпоследовательностей LCS (Longest Common «RUSSIAN FEDERATION», чем к «USA». Однако Subsequence) численно оценивает близость сим- нормирование по средней длине резко разворачива- вольных строк длиной 𝑑𝑑𝑙𝑙 (𝑎𝑎, 𝑏𝑏) выделенной подпо- ет неравенство в обратную сторону: следовательности. Расстояние Левенштейна 𝑑𝑑𝑙𝑙 (𝑎𝑎, 𝑏𝑏) равно количеству символов, не вошедших в длин- 2𝜇𝜇(𝑢𝑢,𝑟𝑟) 2 1 2𝜇𝜇�𝑟𝑟,𝑟𝑟𝑓𝑓 � нейшую общую подпоследовательность. Поэтому |𝑢𝑢|+|𝑟𝑟| = 3 > 2 = |𝑟𝑟|+�𝑟𝑟𝑓𝑓 � . 𝜇𝜇𝑙𝑙 (𝑎𝑎, 𝑏𝑏) + 𝑑𝑑𝑙𝑙 (𝑎𝑎, 𝑏𝑏) = |𝑎𝑎| + |𝑏𝑏|, где 𝑎𝑎 и 𝑏𝑏 – длины Нормализация по [6, 7] даёт ту же ошибку: строк. 𝜇𝜇(𝑢𝑢,𝑟𝑟) 1 1 𝜇𝜇�𝑟𝑟,𝑟𝑟𝑓𝑓 � Вопрос «Сходство или расстояние: Важно ли?» = > = . |𝑢𝑢|+|𝑟𝑟|−𝜇𝜇(𝑢𝑢,𝑟𝑟) 2 3 |𝑟𝑟|+�𝑟𝑟𝑓𝑓 �−𝜇𝜇�𝑟𝑟,𝑟𝑟𝑓𝑓 � не случайно возник в [6]. С ним связаны распро- страненные в научной литературе опасные за- Менее опасно, но также не корректно в этом блуждения. примере нормирование к минимальной длине: 𝜇𝜇�𝑟𝑟,𝑟𝑟𝑓𝑓 � 1 Ошибочное использование метрики 𝜇𝜇(𝑢𝑢,𝑟𝑟) =1= . min(|𝑢𝑢|,|𝑟𝑟|) min�|𝑟𝑟|,�𝑟𝑟𝑓𝑓 �� Хотя некорректность применения метрики Ле- венштейна к строкам различной длины замечена Вывод 2. Нормирование меры сходства риско- ещё в [10], возможная неэквивалентность меры ванно при значимых различиях в длине строк сходства метрике близости отмечена лишь в [8], а Примерно половина наиболее активно цитируе- возможная несводимость меры сходства к метрике мых и используемых определений мер сходства по- близости – в [4], но уже в [7] желание использовать стулирует диапазон значений 𝜇𝜇(𝑥𝑥, 𝑦𝑦) ≤ 𝜇𝜇(𝑥𝑥, 𝑥𝑥) = 1. методы метрического пространства снова прово- Мы видели, как это порождает ошибки при работе цирует спорный вывод: «we have explored the rela- со строками. tion between the concepts of distance and similarity and Сформулированные замечания значимы не толь- shown that adopting the axiomatic definition of simi- ко для географических названий, но и для любых larity as presented here, leads to a spatial interpretation приложений, в которых близость длин не является of similarity as “direction”, complementary to доминирующим признаком сходства. Во всех при- distance». ложениях, перечисленных в начале статьи, это Анализ неудачной попытки нормализации дан- именно так, и в каждом из них нетрудно привести ных НСКФ-2016 выявил плохую работу метрики аналогичные примеры. Исключение, к которому Левенштейна и контрпример к этому утверждению: предостережения данной статьи отношения не име- ют, – это задача исправления ошибок набора текста Хотя сходство строки 𝑝𝑝=«Переславль» со стро- с естественным доминированием близости длин. кой 𝑝𝑝𝑧𝑧 =«Переславль-Залесский», очевидно, значи- тельно выше, чем со строкой 𝑡𝑡=«Тверь» 2 Информативность общей подпоследо- 𝜇𝜇𝑙𝑙 (𝑝𝑝, 𝑝𝑝𝑧𝑧 ) = 9 > 3 = 𝜇𝜇𝑙𝑙 (𝑝𝑝, 𝑡𝑡), вательности но по расстоянию «Переславль» значительно ближе Выравнивание строк выделяет общую подпосле- к «Тверь» довательность. Например, общая подпоследователь- ность («с», «в») строк «Переславль» и «Москва» со- 𝑑𝑑𝑙𝑙 (𝑝𝑝, 𝑝𝑝𝑧𝑧 ) = 11 > 7 = 𝑑𝑑𝑙𝑙 (𝑝𝑝, 𝑡𝑡). ответствует нескольким практически равноценным Мы видим, что упомянутая простая связь НЕ озна- выравниваниям чает, что расстояние и сходство всегда противопо- ложно направлены. Поэтому любой корректный 178 В известных приложениях носителями информа- текает полезное свойство индикация подстроки ции являются подстроки сопоставляемых строк 𝑦𝑦 ⊂ 𝑥𝑥 ⟹ 𝜇𝜇(𝑥𝑥, 𝑦𝑦) = 𝜇𝜇(𝑦𝑦, 𝑦𝑦), (7) 𝑥𝑥 = (𝑥𝑥1 , . . . , 𝑥𝑥𝑚𝑚 ) и 𝑦𝑦 = (𝑦𝑦1, . . . , 𝑦𝑦𝑛𝑛 ), совпадение кото- рых 𝑥𝑥𝑖𝑖+𝑙𝑙𝑥𝑥 = 𝑦𝑦𝑖𝑖+𝑙𝑙𝑦𝑦 ∀𝑖𝑖 = 1, . . . , 𝑘𝑘 является признаком которым обладает NCS, но LCS не обладает. С дру- гой стороны, LCS обладает простой связью с длиной сходства строк (здесь 𝑠𝑠𝑥𝑥 и 𝑠𝑠𝑦𝑦 – начальные позиции строки подстрок, а 𝑘𝑘 – их равная длина, причём �𝑖𝑖 + 𝑠𝑠𝑖𝑖, 𝑖𝑖 + 𝜇𝜇(𝑥𝑥, 𝑥𝑥) = |𝑥𝑥|, (8) 𝑠𝑠𝑦𝑦� – элемент фиксированной общей подпоследова- тельности). Разность начальных позиций 𝑠𝑠𝑥𝑥 − 𝑠𝑠𝑦𝑦 но для NCS это неверно. Диапазон значений у NCS будем называть смещением общей подстроки. Для шире, чем у LCS: 0 ≤ 𝜇𝜇𝑁𝑁 ≤ 𝜓𝜓(min{𝑚𝑚, 𝑛𝑛}). Его верх- строк «RUSSIA» и «USA» таких подстрок в любой няя граница 𝜓𝜓(𝑛𝑛) = 𝑛𝑛(𝑛𝑛 + 1)/2 – треугольное чис- ло, дающее согласно [14] совокупное количество общей подпоследовательности не более, чем четыре подстрок строки длины 𝑛𝑛. (U,US,S,A). Определение 1. Наиболее значимой общей под- 3 Наивный алгоритм вычисления последовательностью назовём такую общую под- Предложенный в [14] алгоритм основан на стан- последовательность, в которой количество общих дартном применении динамического програм- подстрок максимально. Это количество названо в мирования, реализован на С и доступен на CPAN в [13, 15] мерой сходства NCS и будет обозначаться виде компилируемого подгружаемого модуля для 𝜇𝜇𝑁𝑁 (𝑥𝑥, 𝑦𝑦). Perl Algorithm::NCS. С другой стороны, каждый такой признак сход- Алгоритм имеет очевидную оценку сложности ства несёт долю общей информацию. Размер её по памяти 𝑂𝑂(𝑚𝑚𝑚𝑚) и по времени 𝑂𝑂(𝑚𝑚2 𝑛𝑛) через дли- формально оценить невозможно. В текстах могут ны 𝑚𝑚 и 𝑛𝑛 сравниваемых строк. совпасть гениальная фраза либо бессмысленный обрывок, но компьютер этого не разберёт. Для про- Алгоритм 1 стоты удобно считать все их потенциально инфор- #include мационно равноценными. Поскольку каждая строка #include несёт в себе информацию каждой своей подстроки, int t_ocs(char *x, char*y){ int *d, k, i, j, n, m, diag, t; то полный объём общей информации – это снова n = strlen(x)+1; количество всех подстрок 𝜇𝜇𝑁𝑁 (𝑥𝑥, 𝑦𝑦). m = strlen(y)+1; Общее количество подстрок наглядно показано diag = n*m+m; d=calloc(sizeof(int), diag+n+1); количеством указывающих на концы подстроки for (i=1; i d[j*n+i- 1] ? d[(j-1)*n+i] : d[j*n+i-1]; if (x[i-1] == y[j-1]){ Мера сходства 𝜇𝜇 𝑁𝑁 (𝑥𝑥 , 𝑦𝑦 ), очевидно, d[diag -j]++; удовлетворяет классическим аксиомам сходства if (d[j*n+i] < d[j*n+i-n-1]+ [5,7]: неотрицательность d[diag-j]) d[j*n+i] = d[j*n+i-n-1] + 𝜇𝜇(𝑥𝑥, 𝑥𝑥) ≥ 0, (1) d[diag-j];} симметричность else { d[diag -j] = 0;}}} t = d[n*m-1]; 𝜇𝜇(𝑥𝑥, 𝑦𝑦) = 𝜇𝜇(𝑦𝑦, 𝑥𝑥), (2) free(d); return t;} самосходство Для строк небольшой длины алгоритм обладает 𝜇𝜇(𝑥𝑥, 𝑦𝑦) ≤ 𝜇𝜇(𝑥𝑥, 𝑥𝑥), (3) сходным со стандартным для LCS быстродействием (численный эксперимент описан ниже). супераддитивность меры множества общих при- знаков Известные алгоритмы, включая квадратичный [9], требуют квадратичной памяти, что делает их 𝜇𝜇(𝑥𝑥, 𝑦𝑦) + 𝜇𝜇(𝑦𝑦, 𝑧𝑧) ≤ 𝜇𝜇(𝑥𝑥, 𝑧𝑧) + 𝜇𝜇(𝑦𝑦, 𝑦𝑦), (4) неприменимыми для длинных строк. также известная как неравенство покрытия или Простейший подход к оптимизации LCS по ис- аналог неравенства треугольника, и, наконец, инди- пользованию памяти может быть использован и для кация совпадения ускорения работы NCS. 𝜇𝜇(𝑥𝑥, 𝑦𝑦) − 𝜇𝜇(𝑦𝑦, 𝑦𝑦) − 𝜇𝜇(𝑥𝑥, 𝑦𝑦) ⟺ 𝑥𝑥 − 𝑦𝑦. (5) 4 Линейный по памяти алгоритм Кроме классических аксиом, обе меры сходства (NCS и LCS) обладают свойством монотонности Назовём общим окончанием строк макси- мальную общую подстроку, содержащую пару по- 𝑦𝑦 ⊂ 𝑧𝑧 ⟹ 𝜇𝜇(𝑥𝑥, 𝑦𝑦) ≤ 𝜇𝜇(𝑥𝑥, 𝑧𝑧), (6) следних элементов, и эффектным окончанием мак- связанным с вложением подстроки в строку, из ко- симальную часть общего окончания, входящую в торой следует 𝑦𝑦 ⊂ 𝑥𝑥 ⟺ 𝜇𝜇(𝑥𝑥, 𝑦𝑦) = 𝜇𝜇(𝑦𝑦, 𝑦𝑦), но не вы- некоторую наиболее значимую подпоследова- 179 тельность. Стыком общих подстрок будем назы- mu[j] = mx; }}}} else{ /* последние символы различаются */ вать такое их расположение, при котором между ps[s] = 0; ними нет просвета в одной из сравниваемых строк. mu[j] = mx; }} Алгоритм базируется на двух простых леммах, swap (mu,mp); } return mp[n]; приводимых без доказательства. Здесь swap – обмен указателями на массивы. Кор- Лемма 1. Если наиболее значимая общая подпо- ректность кода подтверждена вычислением 1000000 следовательность содержит стык двух общих под- случайных строк с алфавитом из 10 цифр в диапа- строк с разными смещениями, то продолжаться зоне длин до 31×110. через стык может только более короткая из них. В случае равных длин ни одна из строк не может 5 Общность порядка быть продолжена через стык. Чтобы исправить диапазон значений и масштаб Лемма 2. Эффектное окончание стыкуется в NCS, рассмотрим обратную к 𝑡𝑡 = 𝜓𝜓(𝑛𝑛) монотонную наиболее значимой подпоследовательности с кон- вогнутую функцию цом максимальной общей подстроки, представ- √8𝑡𝑡+1−1 ленной в подпоследовательности более длинной, чем 𝑛𝑛 = 𝜑𝜑(𝑡𝑡) = . 2 это окончание, частью. Определение 2. Назовём сходством общности Алгоритм использует вспомогательные массивы порядка (OCS) меру сходства символьных строк, данных для компактного хранения информации: определённую формулой mp[n] хранит ранее вычисленные значения NCS 𝜇𝜇𝑂𝑂 (𝑥𝑥, 𝑦𝑦) = 𝜙𝜙(𝜇𝜇𝑁𝑁 (𝑥𝑥, 𝑦𝑦)). (9) для пар начальных подстрок; Пример 1. Для рассмотренных в начале статьи mu[n] сохраняет текущие вычисляемые значения строк 𝜇𝜇𝑂𝑂 (𝑟𝑟, 𝑢𝑢) ≈ 2.37 < 3. NCS для пар начальных подстрок. Дробное значение отражает квадратично лучшее Используются также массивы данных, индекс разрешение, ценность которого отмечена в [11]. В которых 𝑠𝑠 = 𝑛𝑛 − 𝑗𝑗 + 𝑖𝑖 связан с фиксированной диа- данном случае оно естественно отражает наличие гональю: просвета в выравнивании с «USA», и тем самым ls[s] содержит начальные позиции общих «RUSSIA» оказывается уже не в два, а 2.53 раза окончаний в x для разных смещений; ближе к «RUSSIAN FEDERATION», чем к «USA». le[s] содержит начальные позиции эффектных Теорема 1. Сходство упорядоченной общности, (т .е. включённых в наиболее значимую общую определённое формулой (9), удовлетворяет всем подпоследовательность) общих окончаний. аксиомам (1)–(8). Нулевое значение элемента ls[s] означает несов- Доказательство. Все аксиомы, кроме (4), не- падение окончаний и неактуальность соответству- сложно вытекают из определения. Аксиома (4) вы- ющих значений le[s] и me[s]. текает из следующей леммы. Введённые массивы занимают 3𝑚𝑚 + 8𝑛𝑛 + 5 яче- Лемма 3. Для конечного объединения непересе- ек для хранения целых чисел и инициализируются кающихся отрезков прямой 𝑈𝑈 = ⋃𝑛𝑛𝑘𝑘=1[𝑎𝑎𝑘𝑘 , 𝑏𝑏𝑘𝑘 ] поло- нулями при вызове функции. жим 𝜇𝜇(𝑈𝑈) = ∑𝑛𝑛𝑘𝑘=1 𝜓𝜓(𝑏𝑏𝑘𝑘 − 𝑎𝑎𝑘𝑘 ). Пусть два подмно- жества 𝐴𝐴 и 𝐵𝐵 единичного сегмента [0. 𝑚𝑚] имеют Алгоритм 2 границы, состоящие из конечного числа точек. То- for ( i=1; i < m+1; i++ ){ гда 𝜇𝜇(𝐴𝐴) + 𝜇𝜇(𝐵𝐵) ≤ 𝜇𝜇(𝐴𝐴 ∩ 𝐵𝐵) + 𝑚𝑚. for ( j=1; j < n+1; j++ ){ s = j-i+n; Доказательство леммы основано на возможности mx = max( mp[j], mu[j-1] ); таких перестроек множеств 𝐴𝐴 и 𝐵𝐵, при которых па- if ( x[i-1] == y[j-1] ){ ры сегментов сливаются в один с сохранением веса if ( ps[s] == 0 ){/* окончание длины 1 */ 𝜇𝜇 так, что неравенство леммы усиливается. ps[s] = i; me[s] = mp[j-1]+1; if ( mp[j-1] + 1 > mx ){/* эффектное */ 6 Производительность алгоритмов pe[s] = i; mu[j] = mp[j-1] + 1; } Для сравнения по производительности LCS и else { /* неэффектное */ NCS/OCS были испытаны классический алгоритм pe[s] = i+1; динамического программирования для LCS и выше- mu[j] = mx; }} приведённые алгоритмы, которые мы обозначим по else { /* длина больше 1 */ me[s] += i + 1- ps[s]; порядку NCS1 и NCS2. mt=mp[j-1] + i - pe[s] +1; В цикле длительностью около 20 секунд генери- if ( (me[s] >= mx) && (me[s] >= mt) ){ mu[j] = me[s]; ровались две строки заданных длин, случайно (с pe[s] = ps[s]; } равной вероятностью и независимо) заполненные else { /* доминирует не me[s] */ буквами из алфавита фиксированного размера (2 if ( (mt >= mx) && (mt >= me[s]) ){ или 128), и измерялось сходство между ними. По mu[j] = mt; } else{ /* доминирует mx */ времени и количеству вычислений определялось pe[s] = i+1; среднее время. 180 Полная серия экспериментов для различных пар видимому, не улучшаемы для алгоритмов, работа- длин и мер сходства была повторена три раза и для ющих с разными алфавитами. Для ситуации редких каждой измеренной величины на одном персональ- совпадений, представленной правой половиной таб- ном компьютере Linux PC Intel(R) Core(TM) i3-3250 лички и длинных строк, важной для многих при- CPU @3.50GHz 4 ядра (27935.67 BogoMIPS) 8Gb кладных областей, хорошо известен ряд алгоритмов RAM. Для компенсации случайных флуктуаций бы- вычисления LCS, которые останутся вне конкурен- ли отброшены максимальное и минимальное из ции как минимум до тех пор, пока не проработана каждой тройки полученных значений. Результаты аналогичная оптимизация для NCS. представлены в Таблице 1. 7 Путь к быстрым приближённым алго- Верхняя часть таблицы показывает, что наклад- ритмам ные расходы вызова процедуры доминируют при- Поскольку квадратичная сложность неприемле- мерно до 𝑛𝑛𝑛𝑛 ≈ 10000, а при большем про- ма для поиска сходных подстрок в большой базе изведении длин вступают в силу особенности алго- экспериментальных данных, то острой является по- ритмов. Первый алгоритм NCS оказывается в 2–3 требность в быстрых алгоритмах, надёжно отсеива- раза медленнее, чем LCS, а второй примерно на 30% ющих основную часть несхожей информации, что- медленнее при малых длинах, но неожиданно быст- бы малую оставшуюся часть обработать алгоритма- рее LCS в 2–4 раза на больших. ми, точно оценивающими сходство. Возможная причина в том, что даже при фор- Корень проблемы в том, что любой алгоритм мально большем числе операций массивы компакт- оценки сходства символьных строк базируется на ного хранения могут реже требовать изменений (ес- попарном сравнении элементов. ли данное не изменилось, запись не производится), а Гипотеза 1. Пусть в квадратной таблице раз- операции чтения и особенно сравнения выполняют- мером 2𝑛𝑛 × 2𝑛𝑛 отмечено 𝑛𝑛2 клеток. Тогда в ней ся быстрее, чем операции записи. Для проверки этой можно выбрать последовательность из 𝑛𝑛 неотме- гипотезы в алгоритме строки mu[j] = mx; были за- ченных клеток, у которой номера строк и номера менены на столбцов строго возрастают. if (mu[j] != mx) Отметка клеток, наиболее удалённых от побоч- mu[j] = mx; ной диагонали, образующая два треугольника, один и аналогично дополнена строка ps[s] = 0; в ре- чуть больше другого, по-видимому даёт ситуацию, зультате время практически не изменилось для би- единственную с точностью до центральной симмет- нарного алфавита, но однозначно сократилось рии, в которой более длинных последовательностей в среднем примерно на 0.15 нс для алфавита из 128 нет. символов, что подтвердило гипотезу. Другая воз- Если гипотеза 1 верна, то LCS принципиально не можная причина в том, что процедуры, работающие допускает приближённых алгоритмов поиска с с данными небольших размеров, могут исполняться лучшей, чем квадратичная, оценкой, пригодных для в кэше процессора с более быстрыми обращениями предварительной фильтрации при поиске. Это со- к памяти. В любом случае результаты тестов убеди- гласуется с давно известной [2] невозможностью тельно показали, что на этих случайных данных точного работающего с алфавитами любых разме- скорость работы алгоритмов достаточно близка, и ров алгоритма для LCS с лучшей, чем квадратичная, разумно организовать эксперимент на реальных оценкой сложности. данных. Благодаря чувствительности к просветам, ситуа- Важно отметить, что все известные оптимизации ция для ОCS (и NCS) отличается принципиально: LCS теряют преимущества при работе со случай- ными бинарными последовательностями, и цифры в Теорема 2. Для любого 𝜀𝜀 > 0 существует такой левой половине таблицы и верхних строках, по- номер 𝑁𝑁 > 0, что при любых 𝑚𝑚, 𝑛𝑛 > 𝑁𝑁 можно ука- зать менее 𝑚𝑚𝜀𝜀 −2 пар элементов, несовпадение ко- 181 торых влечёт неравенство 𝜇𝜇𝑂𝑂 (𝑥𝑥, 𝑦𝑦) < 𝜀𝜀 𝑛𝑛. положено левее семейства для 𝐿𝐿 𝜇𝜇 (𝑥𝑥,𝑦𝑦) , два крайних 𝑚𝑚 Сформулированная теорема по сути означает справа представлены точкой (1,1). существование алгоритма предварительной филь- трации при поиске, использующего сравнение При отношении длин 3:13 и ниже для строк сум- 𝑚𝑚 𝜀𝜀 −2 пар элементов. При фиксированной относи- марной длины 1024 символа мы не получаем из LCS тельной погрешности 𝜀𝜀 это означает линейную никакой информации, поскольку результат пред- сложность алгоритма для 𝑚𝑚 = 𝑛𝑛. Искомый алгоритм определён с вероятностью, близкой к 1. При рас- может быть получен предположительно несложной смотренных отношениях строк LCS, как правило, доработкой NCS2. превышает 0.6 от максимального значения, а диапа- зон изменения NCS оказывается больше в разы. Доказательство. Зафиксируем 𝑘𝑘, равное целой Низкие математическое ожидание и дисперсия части от (𝑛𝑛 + 1)𝜀𝜀 2 , и рассмотрим множество из не означают низкую вероятность значимого сходства, 𝑚𝑚𝑚𝑚 более чем пар: {(𝑖𝑖, 𝑗𝑗): 𝑗𝑗 mod 𝑘𝑘 = 0}. Любая об- которую можно интерпретировать как устойчивость 𝑘𝑘 щая подпоследовательность вне этого множества к случайному шуму. пар не может иметь вес, больший чем Рис. 2 показывает, что при увеличении алфавита 𝑛𝑛 𝑘𝑘−1 ситуация меняется количественно, но качественный 𝜙𝜙 �� + 1� 𝜓𝜓(𝑘𝑘 − 1)� = 𝜙𝜙 �𝑛𝑛 � ≤ 𝜀𝜀𝜀𝜀. □ 𝑘𝑘 2 разрыв сохраняется. Можно предположить, что десятилетия интен- сивных многоплановых поисков [1] замены базовых эвристических алгоритмов биоинформатики не уступающими в производительности, но аккуратно теоретически обоснованными, не дали результата потому, что поиски велись вдали от OCS. 8 Устойчивость к случайному шуму Канонический набор данных для тестирования мер сходства составляют случайно генерированные строки, позволяющие объективно оценить важные для приложений качества мер сходства. В частно- сти, строки четырёхбуквенного алфавита с незави- симым и равномерным распределением букв Рисунок 2 Кумулятивные гистограммы меры успешно моделируют объекты биоинформатики. общности пары случайных строк суммарной дли- В ходе численного эксперимента на том же ком- ны 𝑚𝑚 + 𝑛𝑛 = 1024 для алфавита из 128 букв; cлева пьютере получены представленные на Рис. 1 куму- направо отношения длин последовательностей лятивные гистограммы (эмпирические функции m:n= 1:1, 7:9, 3:5, 5:11, 1:3, 3:13, 1:6, 1:15; cемей- 𝜇𝜇 (𝑥𝑥,𝑦𝑦) распределения) значений мер сходства LCS и OCS ство графиков для 𝑂𝑂 расположено левее се- 𝑚𝑚 строк фиксированных длин из равновероятных не- 𝜇𝜇𝐿𝐿 (𝑥𝑥,𝑦𝑦) зависимых букв четырёхбуквенного алфавита. мейства для 𝑚𝑚 Рисунок 1 Кумулятивные гистограммы меры Рис. 3 и 4 демонстрируют значимое усиление эф- фекта по мере роста длин сравниваемых строк. общности пары случайных строк суммарной дли- ны 𝑚𝑚 + 𝑛𝑛 = 1024; cлева направо отношения длин последовательностей m:n= 1:1, 7:9, 3:5, 5:11, 1:3, Рисунок 3 Зависимость математического ожида- 𝜇𝜇 (𝑥𝑥,𝑦𝑦) 3:13, 1:6, 1:15; cемейство графиков для 𝑂𝑂 рас- ния мер общности для четырёхбуквенного алфави- 𝑚𝑚 та от длины кратчайшей из строк при фиксирован- ных отношениях длин 182 larity Metric. IEEE Transactions on Information Theory, 50 (12), pp. 3250-3264 (2004) [5] Chen, S., Ma, B., Zhang, K.: On the Similarity Metric and the Distance Metric. Theoretical Com- puter Science, 410 (24–25), pp. 2365-2376 (2009) [6] Elzinga, C. H.: Distance, Similarity and Sequence Comparison. Advances in Sequence Analysis: Theory, Method, Applications. Springer Interna- tional Publishing, pp. 51-73 (2014) [7] Elzinga, C. H., Studer, M.: Normalization of Dis- tance and Similarity in Sequence Analysis. LaCO- SA II, Lausanne, June 8–10, pp. 445-468 (2016) [8] Emms, M., Franco-Penya, H. H.: On the Expres- Рисунок 4 Зависимость дисперсии мер общности sivity of Alignment-Based Distance and Similarity для четырёхбуквенного алфавита от длины крат- Measures on Sequences and Trees in Inducing Or- чайшей из строк при фиксированных отношениях derings. Springer Proceedings in Mathematics & длин Statistics, 30, pp. 1-18 (2013) [9] Guo, Y.-P., Peng, Y.-H., Yang, C.-B.: Efficient При отношении длин 3:13 и ниже для строк Algorithms for the Flexible Longest Common суммарной длины 1024 символа мы не получаем из Subsequence Problem. Proc. of the 31st Workshop LCS никакой информации, поскольку результат on Combinatorial Mathematics and Computation предопределён с вероятностью, близкой к 1. При Theory, pp. 1-8 (2014) рассмотренных отношениях строк LCS, как прави- [10] Lim, S. Cleansing Noisy City Names in Spatial ло, превышает 0.6 от максимального значения, а Data Mining. 2010 Int. Conf. on Information Sci- диапазон изменения NCS оказывается больше в ра- ence and Applications (ICISA), p. 18 (2010) зы. Низкие математическое ожидание и дисперсия [11] Tseng, K.-T., Yang, C.-B., Huang, K.-S.: The Bet- означают низкую вероятность значимого сходства, ter Alignment Among Output Alignments. J. of которую можно интерпретировать как устойчи- Computers, 3, pp. 51-62 (2007) вость к случайному шуму. [12] Wang, C., Yan, R. X., Wang, X. F., Si, J. N., Zhang, Z.: Comparison of Linear Gap Penalties Заключение and Profile-Based Variable Gap Penalties in Pro- file-Profile Alignments. Computational Biology Описана мера близости, обладающая естествен- and Chemistry, 35 (5), pp. 308-318 (2011) ным определением, уникальным сочетанием полез- ных аксиом (1)–(8), сопоставимыми по сложности и [13] Znamenskij, S. V.: A Model and Algorithm for скорости алгоритмами, повышенными разрешением Sequence Alignment. Program systems: theory и устойчивостью к случайному шуму в сравнении с and applications, 6 (1), pp. 189-197 (2015) LCS. [14] Znamenskij, S. V.: Simple Essential Improve- Выбор других мер сходства для объективного ments to ROUGE-W algorithm. J. of Siberian сравнения сильно затруднён множественностью Federal University. Mathematics & Physics, 4, pp. потенциально возможных интуитивно непрозрач- 258-270 (2015) ных настроек, таких, как коэффициенты широко [15] Znamenskij, S. V.: A Belief Framework for Simi- используемой в биоинформатике функции просве- larity Evaluation of Textual or Structured Data. тов (gap function) [3, 12]. Similarity Search and Applications, LNCS 9371, pp. 138-149 (2015) Литература [1] Abboud, A., Williams, V. V., Weimann, O.: Con- sequences of Faster Alignment of Sequences. Int. Colloquium on Automata, Languages, and Pro- gramming. Springer Berlin Heidelberg, pp. 39-51 (2014) [2] Aho, A. D., Hirschberg, D. S., Ullman, J. D.: Bounds on the Complexity of-the Maximal Com- mon Subsequence Problem. JACM, 23 (1), pp. 1- 12 (1976) [3] Cartwright, R. A.: Logarithmic Gap Costs De- crease Alignment Accuracy. BMC Bioinformatics, 7, 527 (2006) [4] Chen, M., Li X., Ma, B., Vitányi, P. M.: The Simi- 183