|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman A. Kirillov aka Sigizmund 2:5057/21.63 13 Apr 2003 21:50:10
To : Zahar Kiselev
Subject : Re: Разбор почтового адреса.
--------------------------------------------------------------------------------
Было дело - *13.04.03* *18:39:54* ты неосторожно сказал в
конференции *RU.ALGORITHMS* грозному *Oleg Khrulev*
слово о *"Разбор почтового адреса."*.
ZK> Hу и в заключение - поделюсь своей мечтой - встроить этот алгоритм в
ZK> проигрыватель mp3 (xmms), чтобы при сортировке плэйлиста похожие названия
ZK> оказывались рядом и можно было легко искать дубли. Hо я пока не знаю, как
ZK> на основе этого алгоритма написать сортировку.
Хм.. можно сделать например так:
1. Зачитываются названия всех песен в память.
2. Берется первая песня. Для нее ищутся все песни, для которых метрика
Левенштайна, деленная на число символов в названии меньше наперед заданного
\epsilon
3. Данные песни располагаем рядом, с сортировкой по возрастанию отклонения от
данного, соответственно из списка неотсортированных их выбрасываем.
4. Берем следующую по порядку песню...
Алгоритм туповат, сложность O(n^{2}), но за счет хитрых отсечений в процессе
вычисления метрики Л., можно снизить сложность в среднем в два раза.
Имхо так...
Прощай же - но помни...
--- WP/95 Rel 1.78E (215.0) Reg.
* Origin: Ha-ha-ha! (2:5057/21.63)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
