|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 04 Aug 2003 07:48:28
To : Galina O.Ivanova
Subject : Re: Реализация соединения в реляционных БД по "хитрому" условию
--------------------------------------------------------------------------------
"Galina O.Ivanova" wrote:
>
> Anatoly Saveliev пишет:
> AS> Свидетельство только того, что запрос написан
> неграмотно.
>
> Первую грубую проверку делала на C++, записи в обычном
> текстовом файле. Все считывалось в память. В цикле
> вызывала функцию подсчета расстояния. Время работы
> засекалось только для вычисления (не учитывались
> дисковые операции). Если даже я тормозно реализовала
> процедуру вычисления расстояния Левенштейна --
> вообще-то для двух строк классическим методом --
> ну пусть в 10 раз, и у меня для 400 х 400 строк
> длины 35 вышло 19 секунд, то для 400 000 х 500 000
> ничего не светит.
> Исходник могу кинуть мылом, да только нет там ничего
> интересного.
>
> Потому и спрашиваю, как бы мне уйти от m x n вызовов
> своей функции?
Пишу по памяти, ссылки и прочее вспомнить я не смог :-)
Если мне не изменяет память, для сравнения строк делается кэш-функция
примерно следующим образом: если мы используем только русские буквы, то
их (без ъ) 32 штуки, что соотвествует 32 битам, поэтому каждое слово
переводится в битовую маску наличия в нем букв. Если расстояние Хэминга
деленое на число букв меньше порога, то расстояние Левенштейна не
считаем (подобные меры сходства применяются в экологии для сравнения
видового состава, это индекс сходства Симпсона и т.д.) - это позволяет
сократить перебор, поскольку такое сравнение может быть реализовано
очень эффективно. После этого полученные коды для словаря (эталонного
или просто меньшего набора слов) индексируются, т.е. делятся на классы,
вот этот алгоритм я и забыл (что-то из дискретной математики) :-((
Смысл его в том, что полученные коды рассматриваются как множества, и
строится дерево, в узлах которого стоят пересечения множеств-листьев.
Помню только, что некоторые использовали для этого нейронную сеть ART
(Adaptive Resonanse Theory), а некоторые - SOM (Self Organizing Map) -
WebSOM project.
С наилучшими пожеланиями,
Анатолий Савельев
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
