Алгоритм опознавания и сравнения текстов
Invite pending
Алгоритм опознавания и сравнения текстов предназначен для поиска плагиата и повторов в текстах. Реализован в Text::Distill.
Прямое сравнение текстов является крайне ресурсоёмким и алгоритмически сложным. Оно исключает возможность быстрого поиска похожего текста. Требуется механизм, который позволит, опираясь на индексированные поля в БД, найти похожий текст без длительных и сложных вычислений.
Стандартным решением для ускоренного сравнения файлов является построение контрольной суммы (подписи), например CRC32, SHA256, MD5 и проч. Однако, у такого подхода есть очевидный недостаток: минимальные изменения в тексте полностью меняют подпись и два десятимегабайтных документа будут признаны разными, если в одном из них есть пустая строка в конце — а в другом нет.
Стандартная чистка и преобразование текста в матрицу-вектор частотности слов позволяет сравнить тексты безотносительно к порядку слов. Однако такой метод страдает несколькими недостатками:
В принципе, это то что нужно в плане сравнения. Но это совершенно не то, что нужно, в плане производительности — никаких возможностей проиндексировать тексты и сравнить их “по-быстрому”.
Прежде чем строить хэш текст следует “свернуть” текст, исключив все несущественные для поиска копий детали, которые в силу ошибок OCR или умышленной атаки на алгоритм сравнения могут быть добавлены в файл. Убираем знаки препинания, непонятные конструкции вида [стр56], нормализуем UTF8, приводим всё в нижний регистр и упрощаем сложные знаки, например преобразуем “ё” в “е”, а “й” в “й”. Замысел состоит в том, что два похожих текста, скорей всего, и после такой нормализации останутся похожими, а два непохожих — непохожими.
Следующим шагом мы убираем все короткие слова. Для кирилицы считаем короткими слова 6 букв и меньше, для латиницы 5 и меньше. Как правило тексты, даже посвященные одной теме и состоящие из приблизительно тех же слов, будут включать большие слова на разных позициях. При этом мелкие вариации мы опускаем, что радикально уменьшает объём сверяемого текста без заметной деградации уникальности.
Для надежного опознания слова нам не нужны гласные. Более того, для большинства слов нам даже согласные не нужны, достаточно их классификации — звонкая, мягкая, шипящая. Так что следующим этапом сворачивания у нас идёт удаление гласных и приведение оставшихся согласных к их групповому эквиваленту. Аналогичный алгоритм называется Soundex и используется в английском для поиска слов с похожим звучанием. По прямому назначению использовать его в русском языке нельзя, он даёт слишком большие погрешности для единичного слова, но в нашем случае, когда мы хотим опознавать фрагменты текста, оставшейся информации более, чем достаточно.
В итоге у нас получается строка из цифр 1-7, разбитая пробелами на слова. Вот таблица преобразования:
Для дальнейшего сокращения мы всем “словам” длинней 4-х знаков (слова с 5-ю или более согласными) обрежем лишнее, поставив им знак 8 на место отсеченного окончания. Т.е. знак 8 у нас отмечает особенно длинные слова.
Затем удаляем пробелы, получаем однородный “свернутый” текст. Мы отбрасываем существовавшую в изначальном тексте разбивку на абзацы, предложения, главы и проч — у нас остаётся от текста только длинная последовательность цифр 1-8. Полученная строка уже во много раз короче, чем исходный текст. Если нам требуется сравнение повышенной точности можно использовать её, это в любом случае будет намного эффективнее по вычислительным ресурсам, чем сравнение первичных текстов.
При рассечении на фрагменты мы не можем опираться на структуру исходного текста, так как структура наиболее подвержена атакам: точки можно заменить на точки с запятой, какие-то абзацы разбить, а какие-то склеить без какого либо значимого ущерба для читаемости текста.
Поэтому мы проанализируем статистику встречаемости последовательностей на реальных книгах и выделим 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% от исходного текста. Эти чексуммы можно поместить в индексированное поле в БД и находить совпадения с минимальными затратами вычислительных ресурсов.
Соответственно, имея в БД чексуммы по всем известным нам текстам, мы можем, выделив чексуммы из произвольного текстового файла, сравнить их с известными. Если между двумя текстами есть множество совпадений — значит тексты либо содержат массовые заимствования, либо являются “зашумленными” копиями. Боевые испытания выявили у алгоритма возможность выделения даже более-менее обширных цитат.
1. Распознавание текста
Прямое сравнение текстов является крайне ресурсоёмким и алгоритмически сложным. Оно исключает возможность быстрого поиска похожего текста. Требуется механизм, который позволит, опираясь на индексированные поля в БД, найти похожий текст без длительных и сложных вычислений.
1.1 Стандартное, но негодное решение: хэш
Стандартным решением для ускоренного сравнения файлов является построение контрольной суммы (подписи), например CRC32, SHA256, MD5 и проч. Однако, у такого подхода есть очевидный недостаток: минимальные изменения в тексте полностью меняют подпись и два десятимегабайтных документа будут признаны разными, если в одном из них есть пустая строка в конце — а в другом нет.
1.2 Стандартное, но негодное решение: вектор
Стандартная чистка и преобразование текста в матрицу-вектор частотности слов позволяет сравнить тексты безотносительно к порядку слов. Однако такой метод страдает несколькими недостатками:
- Опознает “дубль” в двух очень близких по смыслу и набору слов, но совершенно отличных текстах
- Не позволяет достоверно сравнить фрагмент с целым (опознать рассказ, входящий в сборник, например)
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 Сравнение чексумм
Соответственно, имея в БД чексуммы по всем известным нам текстам, мы можем, выделив чексуммы из произвольного текстового файла, сравнить их с известными. Если между двумя текстами есть множество совпадений — значит тексты либо содержат массовые заимствования, либо являются “зашумленными” копиями. Боевые испытания выявили у алгоритма возможность выделения даже более-менее обширных цитат.