Доклады о будущих и современных технологиях

АЛГОРИТМ БЫСТРОГО НАХОЖДЕНИЯ ЧАСТИЧНО ПОДОБНЫХ ТЕКСТОВ

Е. В. Шарапова

Научный руководитель - А. Л. Жизняков, д-р техн. наук, профессор Муромский институт Владимирского государственного университета

Одной из актуальных задач, возникающих в современном компьюте­ризированном обществе, является нахождение документов, полностью и частично похожих друг на друга. В связи с большим объемом текстов пря­мой поиск по словам - очень трудоемкая задача. Поэтому требуется ис­пользование более быстрых алгоритмов сравнения документов. Для этого можно использовать шинглы. Шингл в переводе с английского языка - «чешуйка». На такие «чешуйки», шинглы, делятся оба рассматриваемых текста. Деление на шинглы может осуществляться по-разному. Они могут идти друг за другом (встык), могут перекрывать друг друга (внахлест), мо­гут идти через некоторое расстояние друг от друга, пропуская несколько символов или слов. Шингл может содержать одну букву или одно слово, а может предложение или несколько предложений. От величины шингла за­висит качество и точность сопоставления документов. Чем больше ШиНгл, тем больше разброс вероятности заимствования. Это ведет к неправиль­ным результатам сравнения (вероятности совпадения). Если шингл ма­ленький (1-2 символа), то точность сравнения может быть очень высокой, но вычислительные мощности, затрачиваемые на реализацию системы сравнения с такими шинглами, могут быть слишком велики, ведь одна из главных задач использования шинглов - снизить трудоемкость сравнения документов. Уменьшение сравниваемого текста достигается путем коди­рования шингла, превращением его в какое-то число, например, с помо­щью алгоритмов CRC, MD5. Все коды шинглов документа формируют список кодов, по которому проводится сопоставление. Для ускорения сравнения из шинглов может быть сформирован супершингл, тоже пред­ставляющий собой числовой код. По кодам, полученным путем преобразо­вания шинглов или супершинглов, системой сравнения проводится сопос­тавление документов и определяется вероятность их совпадения. Разные методы деления текста на шинглы могут сильно отличаться по результа­тивности. Если шинглы идут друг за другом (встык), то их подвижка всего лишь одним-двумя символами может изменить весь текст до неузнаваемо­сти для системы сравнения документов, так как подвинутые шинглы будут содержать уже совсем другие слова и символы. Этого эффекта можно из­бежать, если применять метод наложения шинглов (внахлест), либо метод выборочного взятия ШиНглов.