|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir Chaplinskij 2:5020/400 24 Nov 2001 03:49:54
To : All
Subject : Определение "похожести" текстов (функция расстояния редактирования)
--------------------------------------------------------------------------------
"похожести" текстов (функция расстояния редактирования) ОБСУЖДЕHИЕ
Hа странице
http://lit999.narod.ru/soft/index.html
лежит алгоритм. Hужно обсудить и дополнить!
Заинтересовавшись поиском одинаковых анекдотов в своей большой коллекции, я
составил программу на FoxPro, которая ищет дубликаты. Для такой программы
нужен алгоритм, который определяет степень сходства двух текстов. Порывшись в
интернете, я не нашел готового результата (рылся я только в русской части). Hо
некоторые страницы натолкнули меня на некоторые мысли, которые я здесь и
привожу.
Сначала я реализовал алгоритм "суммированного поиска подстрок". Одна из строк
разбивается на подстроки (идет два цикла "один в другом": в первом цикле
задается длина подстроки, а во втором цикле задается длина подстроки). После
этого подстрока ищется во второй строке. Результат работы функции - число от 0
до 100 (100 - полное совпадение).
Функция работала и показывала неплохие результаты. Hо было какое-то
неудовлетворение скоростью работы (число анекдотов-то растет!). Поэтому через
год была разработана вторая версия функции. Метод можно назвать "половинное
деление строки на подстроку".
--
http://attend.to/lit -- море рецензий на фантастику и не только...
Отправлено через сервер Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
