Алгоритм сходства текста

Question

У меня есть два файла субтитров. Мне нужна функция, которая сообщает, представляют ли они один и тот же текст или похожий текст

Иногда комментарии типа «Ветер дует ... музыка играет» только в одном файле. Но 80% процентов содержимого будет таким же. Функция должна возвращать TRUE (файлы представляют один и тот же текст). И иногда есть неправильные написания, такие как 1 вместо l (один - L), как здесь: Она перевела багаж . Конечно, это означает, что функция должна возвращать TRUE.

Мои комментарии:
Функция должна возвращать процент сходства текстов - AGREE

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

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

Answer 1

алгоритм Левенштейна: http://en.wikipedia.org/wiki/Levenshtein_distance

Что-либо, кроме результата нуля, означает, что текст не "идентичен". «Подобный» является мерой того, насколько далеко / близко они находятся. Результатом является целое число.

Answer 2

Для проблемы, которую вы описали (т.е. скомпилировали большие строки), вы можете использовать Cosine Similarity , которая возвращает число от 0 (совершенно другое) до 1 (идентичное), основываясь на термин частота векторы.

Возможно, вы захотите взглянуть на несколько реализаций, которые описаны здесь: Схожесть косинусов

Answer 3

Вы ожидаете слишком многого здесь, похоже, вам придется написать функцию для ваших конкретных нужд. Я бы порекомендовал начать с существующего приложения для сравнения файлов (возможно, diff уже имеет все необходимое) и улучшить его, чтобы обеспечить хорошие результаты для вашего ввода.

Answer 4

Посмотрите на приблизительный grep . Это может дать вам указатели, хотя почти наверняка вы будете плохо работать с большими кусками текста, о которых вы говорите.

РЕДАКТИРОВАТЬ: оригинальная версия agrep не с открытым исходным кодом, поэтому вы можете получить ссылки на версии OSS с http://en.wikipedia.org/wiki/Agrep

Answer 5

Существует множество альтернатив расстоянию Левенштейна. Например, расстояние Яро-Винклера .

Выбор такого алгоритма зависит от языка, типа слов, слов, введенных человеком, и многих других ...

Здесь вы найдете полезную реализацию нескольких алгоритмов в одной библиотеке