Символьные строки над конечным алфавитом используются для компьютерного представления информации различной природы при поиске плагиата, работе с версиями исходного кода программ, распознавании звуков и поиске мелодий, анализе данных биоинформатики, грубой сортировке сырых текстовых историко-географических данных и в других прикладных задачах. Труды XIX Международной конференции «Аналитика и управление данными в областях с интенсивным использованием данных» (DAMDID/ RCDL’2017), Москва, Россия, 10–13 октября 2017 года
Не только численные значения оценки сходства символьных строк, но и основанные на них результаты ранжирования по сходству или кластеризации существенно зависят от непростого выбора способа количественной оценки пары строк в основном среди двух групп:
Метрики близости оценивают расстояние между строками. Для строки и её подстроки – это обычно разность длин. Формально удовлетворяют известным аксиомам метрического пространства.
Меры сходства оценивают размер общей информации либо мощность пересечения множеств признаков. Для строки и её подстроки – это обычно длина подстроки. Неотрицательны и монотонны по включению. Некоторые из них могут считаться мерами в смысле классической теории меры, остальные (включая LCS) формализуются как нечёткие меры Шоке–Суджено на множестве признаков. Часто называются метриками сходства, что порождает не всегда корректную ассоциацию с метрическим пространством. строк.
Классический подход к построению меры сходства символьных строк и состоит в выравнивании строк выделением в каждой из них одинаковых подпоследовательностей символов.
Выбор длиннейшей из всех таких возможных подпоследовательностей LCS (Longest
Common
Subsequence) численно оценивает
близость
символьных строк длиной ( , ) выделенной
подпоследовательности. Расстояние Левенштейна ( , )
равно количеству символов, не вошедших в
длиннейшую общую подпоследовательность. Поэтому
( , ) + ( , ) = | | + | |, где и – длины
Вопрос «Сходство или расстояние: Важно ли?»
не случайно возник в [
метрического пространства снова провоцирует спорный вывод: «we have explored the relation between the concepts of distance and similarity and shown that adopting the axiomatic definition of similarity as presented here, leads to a spatial interpretation of similarity as “direction”, complementary to distance».
Анализ неудачной попытки нормализации данных НСКФ-2016 выявил плохую работу метрики Левенштейна и контрпример к этому утверждению: тельно выше, чем со строкой =«Тверь» кой Хотя сходство строки =«Переславль» со стро=«Переславль-Залесский», очевидно, значи ( , ) = 9 > 3 = ( , ), но по расстоянию «Переславль» значительно ближе к «Тверь»
( , ) = 11 > 7 = ( , ). Мы видим, что упомянутая простая связь НЕ означает, что расстояние и сходство всегда противоположно направлены. Поэтому любой корректный алгоритм, основанный на метрике, ошибётся в этой ситуации. Использование метрики близости в качестве меры сходства на таких данных порождает ошибки в теоретических выводах и приложениях.
Вывод 1. Метрику близости рискованно использовать для кластеризации (или ранжирования) по сходству строк существенно различной длины: различия в длинах маскируют сходство.
1.2 Ошибочное нормирование сходства
Хорошо известно, что метрику можно нормировать без потерь. Простая связь меры близости с метрикой сходства скрывает фундаментальные различия. Ошибки, связанные с нормированием, отчётливо видны на строках = «USA», = «RUSSIA» и = «RUSSIAN
FEDERATION» и мере сходства LCS: ненормированный LCS вполне обоснованно позиционирует
«RUSSIA» в два раза ближе к
«RUSSIAN FEDERATION», чем к « USA». Однако
нормирование по средней длине резко
разворачивает неравенство в обратную сторону:
2 ( , )
| |+| | =
2
3
>
1
2
= | |+
2 , .
Нормализация по [
, | |+ − , .
Менее опасно, но также не корректно в этом примере нормирование к минимальной длине: ( , ) min(| |,| |) = 1 =
, min | |, .
Вывод 2. Нормирование меры сходства рискованно при значимых различиях в длине строк Примерно половина наиболее активно цитируемых и используемых определений мер сходства постулирует диапазон значений ( , ) ≤ ( , ) = 1. Мы видели, как это порождает ошибки при работе со строками.
Сформулированные замечания значимы не только для географических названий, но и для любых приложений, в которых близость длин не является доминирующим признаком сходства. Во всех приложениях, перечисленных в начале статьи, это именно так, и в каждом из них нетрудно привести аналогичные примеры.
Исключение, к которому предостережения данной статьи отношения не имеют, – это задача исправления ошибок набора текста с естественным доминированием близости длин. 2 Информативность общей подпоследовательности
Выравнивание строк выделяет общую подпоследовательность. Например, общая подпоследовательность («с», «в») строк «Переславль» и «Москва» соответствует нескольким практически равноценным выравниваниям В известных приложениях носителями информации являются подстроки сопоставляемых строк = ( 1, . . . , ) и = ( 1, . . . , ), совпадение которых + = + ∀ = 1, . . . , является признаком сходства строк (здесь и –начальные позиции подстрок, а – их равная длина, причём + , + – элемент фиксированной общей подпоследовательности). Разность начальных позиций − будем называть смещением общей подстроки. Для строк «RUSSIA» и «USA» таких подстрок в любой общей подпоследовательности не более, чем четыре (U,US,S,A).
Определение 1. Наиболее значимой общей
подпоследовательностью назовём такую общую
подпоследовательность, в которой количество общих
подстрок максимально. Это количество названо в
[
С другой стороны, каждый такой признак сходства несёт долю общей информацию. Размер её формально оценить невозможно. В текстах могут совпасть гениальная фраза либо бессмысленный обрывок, но компьютер этого не разберёт. Для простоты удобно считать все их потенциально информационно равноценными. Поскольку каждая строка несёт в себе информацию каждой своей подстроки, то полный объём общей информации – это снова количество всех подстрок ( , ).
Общее количество подстрок наглядно показано количеством указывающих на концы подстроки уголков в примерах:
Мера сходства ( , ), очевидно,
удовлетворяет классическим аксиомам сходства
[
( , ) ≥ 0, ( , ) = ( , ), ( , ) ≤ ( , ), (3) супераддитивность меры множества общих признаков
( , ) + ( , ) ≤ ( , ) + ( , ), (4) также известная как неравенство покрытия или аналог неравенства треугольника, и, наконец, индикация совпадения
( , ) − ( , ) − ( , ) ⟺ − . (5) Кроме классических аксиом, обе меры сходства (NCS и LCS) обладают свойством монотонности ⊂ ⟹ ( , ) ≤ ( , ), (6) связанным с вложением подстроки в строку, из которой следует ⊂ ⟺ ( , ) = ( , ), но не вы(1) (2) текает полезное свойство индикация подстроки ⊂ ⟹ ( , ) = ( , ), (7) которым обладает NCS, но LCS не обладает. С другой стороны, LCS обладает простой связью с длиной строки
( , ) = | |, (8)
но для NCS это неверно. Диапазон значений у NCS
шире, чем у LCS: 0 ≤ ≤ (min{ , }). Его
верхняя граница ( ) = ( + 1)/2 – треугольное
число, дающее согласно [
Алгоритм имеет очевидную оценку сложности по памяти ( ) и по времени ( 2 ) через длины и сравниваемых строк. Алгоритм 1 #include <stdlib.h> #include <string.h> 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<n; i++){ diag++; for (j=1; j<m; j++){
d[j*n+i] = d[(j-1)*n+i] > d[j*n+id[diag-j]) d[diag-j];} ? 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]+
d[j*n+i] = d[j*n+i-n-1] + else { d[diag -j] = 0;}}} t = d[n*m-1]; free(d); return t;} Для строк небольшой длины алгоритм обладает сходным со стандартным для LCS быстродействием (численный эксперимент описан ниже).
Известные алгоритмы, включая квадратичный
[
Простейший подход к оптимизации LCS по использованию памяти может быть использован и для ускорения работы NCS. 4 Линейный по памяти алгоритм
Назовём общим окончанием строк максимальную общую подстроку, содержащую пару последних элементов, и эффектным окончанием максимальную часть общего окончания, входящую в некоторую наиболее значимую подпоследовательность. Стыком общих подстрок будем называть такое их расположение, при котором между ними нет просвета в одной из сравниваемых строк.
Алгоритм базируется на двух простых леммах, приводимых без доказательства.
Лемма 1. Если наиболее значимая общая подпоследовательность содержит стык двух общих подстрок с разными смещениями, то продолжаться через стык может только более короткая из них. В случае равных длин ни одна из строк не может быть продолжена через стык.
Лемма 2. Эффектное окончание стыкуется в наиболее значимой подпоследовательности с концом максимальной общей подстроки, представленной в подпоследовательности более длинной, чем это окончание, частью.
Алгоритм использует вспомогательные массивы данных для компактного хранения информации: mp[n] хранит ранее вычисленные значения NCS для пар начальных подстрок;
mu[n] сохраняет текущие вычисляемые значения NCS для пар начальных подстрок.
Используются также массивы данных, индекс + связан с фиксированной диагональю: которых = − ls[s] содержит
начальные позиции общих окончаний в x для разных смещений;
le[s] содержит начальные позиции эффектных (т .е. включённых в наиболее значимую общую подпоследовательность) общих окончаний.
Нулевое значение элемента ls[s] означает несовпадение окончаний и неактуальность соответствующих значений le[s] и me[s].
Введённые массивы занимают 3 + 8 + 5 ячеек для хранения целых чисел и инициализируются нулями при вызове функции. Алгоритм 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] ){ ps[s] = i; me[s] = mp[j-1]+1; pe[s] = i; mu[j] = mp[j-1] + 1; } else { /* неэффектное */ pe[s] = i+1; mu[j] = mx; }} else { /* длина больше 1 */ me[s] += i + 1- ps[s]; mt=mp[j-1] + i - pe[s] +1; if ( ps[s] == 0 ){/* окончание длины 1 */ if ( mp[j-1] + 1 > mx ){/* эффектное */ if ( (me[s] >= mx) && (me[s] >= mt) ){ mu[j] = me[s]; pe[s] = ps[s]; } else { /* доминирует не me[s] */ if ( (mt >= mx) && (mt >= me[s]) ){ mu[j] = mt; } pe[s] = i+1; else{ /* доминирует mx */ else{ /* последние символы различаются */ NCS, рассмотрим обратную к = ( ) монотонную = ( ) = √8 +1−1.
2 Определение 2. Назовём сходством общности порядка (OCS) меру сходства символьных строк, определённую формулой ( , ) = ( ( , )). (9) Пример 1. Для рассмотренных в начале статьи строк ( , ) ≈ 2.37 < 3.
Дробное значение отражает квадратично лучшее
разрешение, ценность которого отмечена в [
Теорема 1. Сходство упорядоченной общности, определённое
формулой (9), удовлетворяет всем аксиомам (1)–(8).
Доказательство. Все аксиомы, кроме (4), несложно вытекают из определения. Аксиома (4) вытекает из следующей леммы.
Лемма 3. Для конечного объединения непересе кающихся отрезков прямой = ⋃ =1[ , ] положества
и жим ( ) = ∑ =1 ( единичного сегмента [0. ] имеют
− ). Пусть два подмнограницы, состоящие из конечного числа точек. Тогда ( ) + ( ) ≤ (
∩ ) + .
Доказательство леммы основано на возможности таких перестроек множеств и , при которых пары сегментов сливаются в один с сохранением веса так, что неравенство леммы усиливается. 6 Производительность алгоритмов Для сравнения по производительности LCS и NCS/OCS были испытаны классический алгоритм динамического программирования для LCS и вышеприведённые алгоритмы, которые мы обозначим по порядку NCS1 и NCS2.
В цикле длительностью около 20 секунд генерировались две строки заданных длин, случайно (с равной вероятностью и независимо) заполненные буквами из алфавита фиксированного размера (2 или 128), и измерялось сходство между ними. По времени и количеству вычислений определялось среднее время.
Полная серия экспериментов для различных пар длин и мер сходства была повторена три раза и для каждой измеренной величины на одном персональном компьютере Linux PC Intel(R) Core(TM) i3-3250 CPU @3.50GHz 4 ядра (27935.67 BogoMIPS) 8Gb RAM. Для компенсации случайных флуктуаций были отброшены максимальное и минимальное из каждой тройки полученных значений. Результаты представлены в Таблице 1.
Верхняя часть таблицы показывает, что накладные расходы вызова процедуры доминируют примерно до ≈ 10000, а при большем произведении длин вступают в силу особенности алгоритмов. Первый алгоритм NCS оказывается в 2–3 раза медленнее, чем LCS, а второй примерно на 30% медленнее при малых длинах, но неожиданно быстрее LCS в 2–4 раза на больших.
Возможная причина в том, что даже при формально большем числе операций массивы компактного хранения могут реже требовать изменений (если данное не изменилось, запись не производится), а операции чтения и особенно сравнения выполняются быстрее, чем операции записи. Для проверки этой гипотезы в алгоритме строки mu[j] = mx; были заменены на if (mu[j] != mx) mu[j] = mx; и аналогично дополнена строка ps[s] = 0; в результате время практически не изменилось для бинарного алфавита, но однозначно сократилось в среднем примерно на 0.15 нс для алфавита из 128 символов, что подтвердило гипотезу. Другая возможная причина в том, что процедуры, работающие с данными небольших размеров, могут исполняться в кэше процессора с более быстрыми обращениями к памяти. В любом случае результаты тестов убедительно показали, что на этих случайных данных скорость работы алгоритмов достаточно близка, и разумно организовать эксперимент на реальных данных.
Важно отметить, что все известные оптимизации LCS теряют преимущества при работе со случайными бинарными последовательностями, и цифры в левой половине таблицы и верхних строках, повидимому, не улучшаемы для алгоритмов, работающих с разными алфавитами. Для ситуации редких совпадений, представленной правой половиной таблички и длинных строк, важной для многих прикладных областей, хорошо известен ряд алгоритмов вычисления LCS, которые останутся вне конкуренции как минимум до тех пор, пока не проработана аналогичная оптимизация для NCS. 7 Путь к быстрым приближённым алгоритмам
Поскольку квадратичная сложность неприемлема для поиска сходных подстрок в большой базе экспериментальных данных, то острой является потребность в быстрых алгоритмах, надёжно отсеивающих основную часть несхожей информации, чтобы малую оставшуюся часть обработать алгоритмами, точно оценивающими сходство.
Корень проблемы в том, что любой алгоритм оценки сходства символьных строк базируется на попарном сравнении элементов.
Гипотеза 1. Пусть в квадратной таблице размером 2 × 2 отмечено 2 клеток. Тогда в ней можно выбрать последовательность из неотмеченных клеток, у которой номера строк и номера столбцов строго возрастают.
Отметка клеток, наиболее удалённых от побочной диагонали, образующая два треугольника, один чуть больше другого, по-видимому даёт ситуацию, единственную с точностью до центральной симметрии, в которой более длинных последовательностей нет.
Если гипотеза 1 верна, то LCS принципиально не
допускает приближённых алгоритмов поиска с
лучшей, чем квадратичная, оценкой, пригодных для
предварительной фильтрации при поиске. Это
согласуется с давно известной [
Благодаря чувствительности к просветам, ситуация для ОCS (и NCS) отличается принципиально: Теорема 2. Для любого > 0 существует такой номер > 0, что при любых , > можно указать менее −2 пар элементов, несовпадение которых влечёт неравенство ( , ) < . Сформулированная теорема по сути означает существование алгоритма предварительной фильтрации при поиске, использующего сравнение −2 пар элементов. При фиксированной относительной погрешности это означает линейную сложность алгоритма для = . Искомый алгоритм может быть получен предположительно несложной доработкой NCS2.
Доказательство. Зафиксируем , равное целой части от (
+ 1) 2, и рассмотрим множество из не
более чем пар: {( , ): mod = 0}. Любая
общая подпоследовательность вне этого множества
пар не может иметь вес, больший чем
+ 1 ( − 1) =
−1
2
≤ . □
Можно предположить, что десятилетия
интенсивных многоплановых поисков [
В ходе численного эксперимента на том же компьютере получены представленные на Рис. 1 кумулятивные гистограммы (эмпирические функции распределения) значений мер сходства LCS и OCS строк фиксированных длин из равновероятных независимых букв четырёхбуквенного алфавита. Рисунок 1 Кумулятивные гистограммы меры положено левее семейства для ( , ), два крайних справа представлены точкой (1,1). При отношении длин 3:13 и ниже для строк суммарной длины 1024 символа мы не получаем из LCS никакой информации, поскольку результат предопределён с вероятностью, близкой к 1. При рассмотренных отношениях строк LCS, как правило, превышает 0.6 от максимального значения, а диапазон изменения NCS оказывается больше в разы. Низкие математическое ожидание и дисперсия означают низкую вероятность значимого сходства, которую можно интерпретировать как устойчивость к случайному шуму.
Рис. 2 показывает, что при увеличении алфавита ситуация меняется количественно, но качественный разрыв сохраняется.
мейства для ( , )
Рисунок 2 Кумулятивные гистограммы меры общности пары случайных строк суммарной длины
+ = 1024 для алфавита из 128 букв; cлева направо отношения длин последовательностей m:n= 1:1, 7:9, 3:5, 5:11, 1:3, 3:13, 1:6, 1:15; cемейство графиков для ( , ) расположено левее се Рис. 3 и 4 демонстрируют значимое усиление эффекта по мере роста длин сравниваемых строк. общности пары случайных строк суммарной длины +
= 1024; cлева направо отношения длин последовательностей m:n= 1:1, 7:9, 3:5, 5:11, 1:3, 3:13, 1:6, 1:15; cемейство графиков для ( , ) рас
Рисунок 3 Зависимость математического ожидания мер общности для четырёхбуквенного алфавита от длины кратчайшей из строк при фиксированных отношениях длин Рисунок 4 Зависимость дисперсии мер общности для четырёхбуквенного алфавита от длины кратчайшей из строк при фиксированных отношениях длин
При отношении длин 3:13 и ниже для строк суммарной длины 1024 символа мы не получаем из LCS никакой информации, поскольку результат предопределён с вероятностью, близкой к 1. При рассмотренных отношениях строк LCS, как правило, превышает 0.6 от максимального значения, а диапазон изменения NCS оказывается больше в разы. Низкие математическое ожидание и дисперсия означают низкую вероятность значимого сходства, которую можно интерпретировать как устойчивость к случайному шуму. Заключение
Описана мера близости, обладающая естественным определением, уникальным сочетанием полезных аксиом (1)–(8), сопоставимыми по сложности и скорости алгоритмами, повышенными разрешением и устойчивостью к случайному шуму в сравнении с LCS.
Выбор других мер сходства для объективного
сравнения сильно затруднён множественностью
потенциально возможных интуитивно
непрозрачных настроек, таких, как коэффициенты широко
используемой в биоинформатике функции
просветов (gap function) [