|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 03 Oct 2001 21:36:46
To : Andrey Dudko
Subject : Похожесть стpок
--------------------------------------------------------------------------------
AA>> Суть алгоритма заключается в том, чтобы подсчитать количество
AA>> совпадающих последовательных букв в "сравниваемых" словах. Причем
AA>> совпадающие буквы необязательно должны идти строго друг за
AA>> другом. Слова с наибольшим количеством совпадающих букв и будут
AA>> похожими. Кроме того, анализ производится не только с начала
AA>> тестируемого слова но и может начинаться с других его позиций.
AD>
AD> А я делал немножко по-дpугому. Составил таблицу "стоимости" замены
AD> каждой буквы на каждую букву, таблицы "стоимости" вставки буквы и
AD> удаления буквы, пеpестановка двух любых соседних букв (задана одна на
AD> всех), а также "стоимости" "сложных замен" (под сложными заменами я
AD> подpазумевал замены последовательность <--> последовательность,
AD> напpимеp, "сч" <--> "щ"). В пpинципе, все замены/удаления/вставки
AD> можно считать частным случаем сложных замен, но так, имхо,
AD> обpабатывать быстpее.
Hу хорошо. Видимо, мне нужно написать крохотную научную работу в этой области.
Жалко что мало времени. Это как раз то место, где работает математика.
Когда я думал над алгоритмикой, то понял что реально эту задачу про похожесть
слов можно математически свести к теории n-мерных пространств.
Каждое слово будет вектором.
Для оценки похожести слов, необходимо вычислить расстояние между векторами в
пространстве.
Основная задача - это векторизация слов, Т.е. размещение их в N-мерном
пространстве.
Простейшее пространство - одномерное. Более совершенно использовать
пространства N-мерные, где слово обладает не одной "координатой" (аттрибутом,
параметром) а несколькими.
Задача векторизации может иметь самые разные решения, в частности, хорошо
сделать пред-обработку, проводить фильтрацию.
Задача пред-обработки, фильтрации состоит в устранении высокочастотного "шума"
и нормализации данных.
После всего этого нужно всего лишь найти расстояние между векторами. Все.
-----
Так вот, твоя "оценка стоимости" это и есть эмпирический перевод в одномерное
пространство, где слова имеют всего одну координату - "стоимость".
--- Alex Raider / Flash inc.
* Origin: Alex Raider/ Flash inc. 1992-2001 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
