Алгоритм опознавания и сравнения текстов

Немного «закулисы» сегодня, давно хотел рассказать, но руки не доходили.

На ЛитРес все книги при запуске в продажу проверяются на плагиат. Мы обнаруживаем полную идентичность, пересечения между текстами, заимствования. Механика особенно полезна при работе с самиздатом, где автор может опубликовать чужой и/или запрещенный к публикации текст, но и для обычных издательских текстов востребована. Так же мы предоставляем открытый API, которым пользуется, например, VK для блокировки раздачи пиратских текстов.

Алгоритм реализован в модуле Text::Distill, исходный код открыт, можно пользоваться. Открыт и API, сверяющий текст с содержимым каталога ЛитРес.

1. Распознавание текста

1.1 Проблема

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

1.2 Стандартное, но негодное решение: хэш

Стандартным решением для ускоренного сравнения файлов является построение контрольной суммы (подписи), например CRC32, SHA256, MD5 и проч. Однако, у такого подхода есть очевидный недостаток: минимальные изменения в тексте полностью меняют подпись и два десятимегабайтных документа будут признаны разными, если в одном из них есть пустая строка в конце - а в другом нет.

1.3 Стандартное, но негодное решение: вектор

Стандартная чистка и преобразование текста в матрицу-вектор частотности слов позволяет сравнить тексты безотносительно к порядку слов. Однако такой метод страдает несколькими недостатками:

  • Опознает “дубль” в двух очень близких по смыслу и набору слов, но совершенно отличных текстах
  • Не позволяет достоверно сравнить фрагмент с целым (опознать рассказ, входящий в сборник, например)

1.3 Стандартное, но негодное решение: Edit distance

В принципе, это то что нужно в плане сравнения. Но это совершенно не то, что нужно, в плане производительности - никаких возможностей проиндексировать тексты и сравнить их “по-быстрому”.

2. Эффективное решение Text::Distill

2.1 Нормализация символов строки

Прежде чем строить хэш текст следует “свернуть” текст, исключив все несущественные для поиска копий детали, которые в силу ошибок OCR или умышленной атаки на алгоритм сравнения могут быть добавлены в файл. Убираем знаки препинания, непонятные конструкции вида [стр56], нормализуем UTF8, приводим всё в нижний регистр и упрощаем сложные знаки, например преобразуем “ё” в “е”, а “й” в “и”. Замысел состоит в том, что два похожих текста, скорей всего, и после такой нормализации останутся похожими, а два непохожих - непохожими.

2.2 Удаление коротких слов

Следующим шагом мы убираем все короткие слова. Для кирилицы считаем короткими слова 6 букв и меньше, для латиницы 5 и меньше. Как правило тексты, даже посвященные одной теме и состоящие из приблизительно тех же слов, будут включать большие слова на разных позициях. При этом мелкие вариации мы опускаем, что радикально уменьшает объём сверяемого текста без заметной деградации уникальности.

2.3 Soundex

Для надежного опознания слова нам не нужны гласные. Более того, для большинства слов нам даже согласные не нужны, достаточно их классификации - звонкая, мягкая, шипящая. Так что следующим этапом сворачивания у нас идёт удаление гласных и приведение оставшихся согласных к их групповому эквиваленту. Аналогичный алгоритм называется Soundex и используется в английском для поиска слов с похожим звучанием. По прямому назначению использовать его в русском языке нельзя, он даёт слишком большие погрешности для единичного слова, но в нашем случае, когда мы хотим опознавать фрагменты текста, оставшейся информации более, чем достаточно.

В итоге у нас получается строка из цифр 1-7, разбитая пробелами на слова. Вот таблица преобразования:

рrлйlбпфвbfpvтдdtжшщчсцзкгхcgjkqsxzмнmn

664441111111133337777222222222222225555

Для дальнейшего сокращения мы всем “словам” длинней 4-х знаков (слова с 5-ю или более согласными) обрежем лишнее, поставив им знак 8 на место отсеченного окончания. Т.е. знак 8 у нас отмечает особенно длинные слова.

Затем удаляем пробелы, получаем однородный “свернутый” текст. Мы отбрасываем существовавшую в изначальном тексте разбивку на абзацы, предложения, главы и прочее - у нас остаётся от текста только длинная последовательность цифр 1-8. Полученная строка уже во много раз короче, чем исходный текст. Если нам требуется сравнение повышенной точности можно использовать её, это в любом случае будет намного эффективнее по вычислительным ресурсам, чем сравнение первичных текстов.

2.4 Рассечение на фрагменты

Для быстрого сопоставления текстов решение из 2.3, несмотря на преимущества, неприемлемо. Нам требуется какой-то слепок, имеющий размер в районе процента от исходного текста или меньше, который мы сможем проиндексировать и эффективно сравнивать. Для этого придется рассечь уже “свёрнутый” текст на фрагменты и с каждого фрагмента снять хэш. Размер фрагментов после рассечения надо подобрать так, чтобы каждый “представлял” ~2кб исходного текста.

При рассечении на фрагменты мы не можем опираться на структуру исходного текста, так как структура наиболее подвержена атакам: точки можно заменить на точки с запятой, какие-то абзацы разбить, а какие-то склеить без какого либо значимого ущерба для читаемости текста.

Поэтому мы проанализируем статистику встречаемости последовательностей на реальных книгах и выделим 4-х символьные последовательности, которые встречаются в текстах с заданной частотой и опираясь на которые мы сможем поделить текст на фрагменты заданного размера. Проанализировав имеющиеся у нас ~200000 текстов удалось выделить следующие последовательности, адекватно работающие для языков ru    en    it    de    fr    es    pl    be    cs    sp    lv

3856 6542 4562 6383 4136 2856 4585 5512 2483 5426 2654 3286 5856 4245 4135 4515 4534 8312 5822 5316 1255 8316 5842

Часть из этих последовательностей редки в русском и английском, но часто встречаются в латвийском, например, но в целом такой набор даёт уверенно разбиение текста на фрагменты, которое весьма затруднительно обойти. Так же статистический анализ текстов даёт несколько сотен альтернативных последовательностей, которые могут быть использованы в качестве “граничных” либо для организации “перпендикулярного” слепка, либо для уменьшения размера фрагмента (если задача детальности опознания более приоритетна, чем скорость).

После рассечения теста на фрагменты мы отбрасываем “свернутые” строки, длина которых меньше 150 знаков, по остальным фрагментам формируем 32-х битный хэш (хеш-функция Дженкинса подходит идеально). В итоге получается набор 32-х битных чексумм, объёмом приблизительно 0,5% от исходного текста. Эти чексуммы можно поместить в индексированное поле в БД и находить совпадения с минимальными затратами вычислительных ресурсов.

2.5 Сравнение чексумм

Соответственно, имея в БД чексуммы по всем известным нам текстам, мы можем, выделив чексуммы из произвольного текстового файла, сравнить их с известными. Если между двумя текстами есть множество совпадений - значит тексты либо содержат массовые заимствования, либо являются “зашумленными” копиями. Боевые испытания выявили у алгоритма возможность обнаружения даже более-менее обширных цитат.

Error

default userpic

Your reply will be screened

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.