Word Tables

Word Tables

А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?

Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

А еще ?

Миша

Re: Word Tables

On Apr 16, 10:05 am, "Mikhail Kimmelman" <mikhail.kimmel...@gmail.com>
wrote:


А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?
Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.
А еще ?


Да как кому удобно, так и хранят (начиная от линейных списков на cons
cells - исторически первый, да и сейчас в некоторых применениях
полезный способ). Тебе зачем?

Kit.

Re: Word Tables

Mikhail Kimmelman wrote:



Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

Есть такое волшебное слово - DB Table. Indexed, конечно.


--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables


А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?



Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.


Suffix tree -- типа trie, только несколько эффективнее, уникальные суффиксы
не разбиваются на буквы.

ещё есть какой-то DAWG: A directed acyclic word graph (DAWG) is a data
structure in computer science similar to a trie but much more space
efficient.

можно ещё вспомнить как словарь компактно записать файл -- записывать только
разницу между предыдущим словом и текущим, т.е. сколько букв убрать в конце
и какие буквы добавить, по идее это весьма эффективное представление (в
отличие от trie не нужно указателей и прочей муры, которая место жрёт со
страшной силой). сам этот формат искать/вставлять/удалять эффективно не
позволяет, но я думаю при желании можно прикрутить рядом индекс для
оптимизации этого дела -- это если список слов реально очень большой, а
изменения не особо частые.



Re: Word Tables



А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?





Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.



а, ну и для полноты можно упомянуть bloom filter, если какое-то количество
ошибок не является критичным.


Re: Word Tables


"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fu44vn$1h7h$1@mamba.crocodile.org...

А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?

Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

А еще ?

вообще таблицы слов, буде таковые растут сверх нормы, хранят в базе данных.

Re: Word Tables

Mikhail Kimmelman wrote:

А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?

Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

А еще ?


Ну так а какие есть дополнительные требования?

- Надо ли изо всех сил экономить память? Т.е надо ли заниматься разнообразным
слиянием одинаковых префиксов и т.п. или нет?

- Надо ли в каждый момент времени поддерживать упорядоченную структуру (on-line
упорядочивание)?

- Какого рода поиск имеется в виду: нужны ли какие-то "размазанные" запросы,
типа поисков с wildcards или вообще regular expressions?

- И т.п.

Если ничего этого не надо, что зачем огород гордить - Hash table-based структура
данных и готово.

--
Best regards,
Andrey Tarasevich

Re: Word Tables


"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:XZadnYDErOClgJvVnZ2dnUVZ_jednZ2d@comcast.com...

Mikhail Kimmelman wrote:

А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?

Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

А еще ?


Ну так а какие есть дополнительные требования?

- Надо ли изо всех сил экономить память? Т.е надо ли заниматься
разнообразным слиянием одинаковых префиксов и т.п. или нет?

- Надо ли в каждый момент времени поддерживать упорядоченную структуру
(on-line упорядочивание)?

- Какого рода поиск имеется в виду: нужны ли какие-то "размазанные"
запросы, типа поисков с wildcards или вообще regular expressions?

- И т.п.

Если ничего этого не надо, что зачем огород гордить - Hash table-based
структура данных и готово.


Все надо. Так что где панацея?


Re: Word Tables

"Nikita V. Belenki" <fido7@kits.net> wrote in message
news:b75e3e74-9250-4a07-bd10-



А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?
Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.
А еще ?


Да как кому удобно, так и хранят (начиная

< от линейных списков на cons cells -

Это как ?


исторически первый, да и сейчас в некоторых применениях
полезный способ). Тебе зачем?


Просто так.

Миша

Re: Word Tables

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu4jpr$3ng$00$1@news.t-online.com...



Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.


Есть такое волшебное слово - DB Table. Indexed, конечно.


Это как ?

Миша

Re: Word Tables

"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:XZadnYDErOClgJvVnZ2dnUVZ_jednZ2d@comcast.com...


Ну так а какие есть дополнительные требования?

- Надо ли изо всех сил экономить память? Т.е надо ли заниматься
разнообразным слиянием одинаковых префиксов и т.п. или нет?

- Надо ли в каждый момент времени поддерживать
упорядоченную структуру (on-line упорядочивание)?

- Какого рода поиск имеется в виду: нужны ли какие-то
"размазанные" запросы, типа поисков с wildcards или
вообще regular expressions?

- И т.п.

Если ничего этого не надо, что зачем огород гордить -
Hash table-based структура данных и готово.


Сначала вроде нужно ничего не нужно было,
и сделали hash table. А теперь еще вроде надо
с wildcards искать.

Миша

Re: Word Tables


"Mikhail Kimmelman" <mikhail.kimmelman@gmail.com> wrote in message
news:fu5kcg$2uq5$1@mamba.crocodile.org...

"Andrey Tarasevich" <andreytarasevich@hotmail.com> wrote in message
news:XZadnYDErOClgJvVnZ2dnUVZ_jednZ2d@comcast.com...


Ну так а какие есть дополнительные требования?

- Надо ли изо всех сил экономить память? Т.е надо ли заниматься
разнообразным слиянием одинаковых префиксов и т.п. или нет?

- Надо ли в каждый момент времени поддерживать
упорядоченную структуру (on-line упорядочивание)?

- Какого рода поиск имеется в виду: нужны ли какие-то
"размазанные" запросы, типа поисков с wildcards или
вообще regular expressions?

- И т.п.

Если ничего этого не надо, что зачем огород гордить -
Hash table-based структура данных и готово.


Сначала вроде нужно ничего не нужно было,
и сделали hash table. А теперь еще вроде надо
с wildcards искать.


надо было сделать на уровне интерфейса что-бы просто менять начинку, а
теперь вам придется все переделывать и неоднократно. Несчастный вы человек.


Re: Word Tables

Mikhail Kimmelman wrote:



Есть такое волшебное слово - DB Table. Indexed, конечно.

Это как ?

А вот так.
Миша но ведь тебе платят не за то, что ты придумывал как словарь хранить, правда?
Поэтому словарь надо хранить в базе данных - программе которая специально
для таких случаев и предназначена, а самому сосредоточиться на решении основной
задачи.

--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables


"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu5pa1$rf9$00$1@news.t-online.com...




Есть такое волшебное слово - DB Table. Indexed, конечно.

Это как ?

А вот так.
Миша но ведь тебе платят не за то, что ты придумывал как словарь хранить,
правда?


Это на самом деле очень сложный вопрос.
Неоднозначный


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


Как даже в совсем коротком предложении
чувствуется истинно немецкий дух.

Миша

Re: Word Tables

Mikhail Kimmelman wrote:


Это на самом деле очень сложный вопрос.
Неоднозначный

Ответ зато однозначен. В программировании мы стоим
на плечах гигантов и на 90 слепо используем их опыт лепя
программу из тех кубиков, что они приготовили .
Есть мнение, что надо использовать лучшие кубики из
имеющихся. В данном случае - это база данных.

По сравнению с технологиями и патентами зашитыми в лучших из
них все твои одинокие бинарные деревья и куцие Hashmaps
и сортировки на коленке - детский лепет.


Как даже в совсем коротком предложении
чувствуется истинно немецкий дух.

воистину это всего-лишь здравый смысл.


--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables

senatov <jakov-senatov@t-online.de> wrote:

Mikhail Kimmelman wrote:




Это на самом деле очень сложный вопрос.
Неоднозначный

Ответ зато однозначен. В программировании мы стоим
на плечах гигантов и на 90 слепо используем их опыт лепя
программу из тех кубиков, что они приготовили .
Есть мнение, что надо использовать лучшие кубики из
имеющихся. В данном случае - это база данных.


А вот это вот - совершенно неочевидно.
Специализированное решение - в большинстве случаев
эффективнее общечеловеческого.


По сравнению с технологиями и патентами зашитыми в лучших из
них все твои одинокие бинарные деревья и куцие Hashmaps
и сортировки на коленке - детский лепет.


Да это тоже ерунда.
Какие-то детские комплексы.
Видимо, от непонимания, что от налепливания лейбла
hash быстрее не становится.



Как даже в совсем коротком предложении
чувствуется истинно немецкий дух.

воистину это всего-лишь здравый смысл.


Не, это eine Colonne marschiert или как там оно было.

---
Const

Re: Word Tables

Const wrote:

senatov <jakov-senatov@t-online.de> wrote:

Mikhail Kimmelman wrote:




Это на самом деле очень сложный вопрос.
Неоднозначный

Ответ зато однозначен. В программировании мы стоим
на плечах гигантов и на 90 слепо используем их опыт лепя
программу из тех кубиков, что они приготовили .
Есть мнение, что надо использовать лучшие кубики из
имеющихся. В данном случае - это база данных.


А вот это вот - совершенно неочевидно.
Специализированное решение - в большинстве случаев
эффективнее общечеловеческого.


Если все приложение заключается в поддержке вот этого единственного
специализированного решения - безусловно. Вот, например, Гугл.

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



По сравнению с технологиями и патентами зашитыми в лучших из
них все твои одинокие бинарные деревья и куцие Hashmaps
и сортировки на коленке - детский лепет.


Да это тоже ерунда.
Какие-то детские комплексы.
Видимо, от непонимания, что от налепливания лейбла
hash быстрее не становится.


Я ничего не имею против того, чтобы Вы эти теории продавали АТТ.
Но мы-то здесь все свои, нет?




Как даже в совсем коротком предложении
чувствуется истинно немецкий дух.

воистину это всего-лишь здравый смысл.


Не, это eine Colonne marschiert или как там оно было.


А как вы боретесь со внутренней противоречивостью, садясь каждый день
в произведение вот этих марширующих колонн?

Re: Word Tables

"Юpa Шaлaк" <jupastor@gmail.com> wrote in message
news:FxxNj.6262$nT1.3974@trndny09...


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


А какую базу данных использует спелчекер в текстовом реадкторе ?

Миша

Re: Word Tables

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu5u0i$oln$01$1@news.t-online.com...


Ответ зато однозначен. В программировании мы стоим
на плечах гигантов и на 90 слепо используем их опыт лепя
программу из тех кубиков, что они приготовили .
Есть мнение, что надо использовать лучшие кубики из
имеющихся. В данном случае - это база данных.


А какую базу данных использует в юниксе комманда spell ?


По сравнению с технологиями и патентами зашитыми в лучших из
них все твои одинокие бинарные деревья и куцие Hashmaps
и сортировки на коленке - детский лепет.


Ух ты. А чем по-Вашему, отличается Сортировка в Лучших Кубиках
к примеру от обычной ?



Как даже в совсем коротком предложении
чувствуется истинно немецкий дух.

воистину это всего-лишь здравый смысл.


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

На одной моей работе например понадобилось
поменять стандарную файловую систему на свою,
нестандартую. Ну, взяли, написали и воткнули в ядро.

Миша

Re: Word Tables

"Alex Mizrahi" <udodenko@users.sourceforge.net> wrote in message
news:fu4l6g$22dm$1@ddt.demos.su...


Suffix tree -- типа trie, только несколько эффективнее,
уникальные суффиксы не разбиваются на буквы.


Здесь, по-моему, немного разные вещи смешаны.

1) suffix tree это trie суфиксов.

2) trie можно хранить компактно, так что каждой вершине
соответствует не одна буква, а несколько (такая структура
данных называется вроде particia).

3) поскольку suffix tree -- очень большое для его хранения
используется (2).


ещё есть какой-то DAWG: A directed acyclic word graph (DAWG) is a data
structure in computer science similar to a trie but much more
space efficient.


Интересно. А можно своими словами ?


можно ещё вспомнить как словарь компактно записать файл -- записывать
только разницу между предыдущим словом и текущим, т.е. сколько букв убрать
в конце и какие буквы добавить, по идее это весьма эффективное
представление (в отличие от trie не нужно указателей и прочей муры,
которая место жрёт со страшной силой). сам этот формат
искать/вставлять/удалять эффективно не позволяет, но я думаю при желании
можно прикрутить рядом индекс для оптимизации этого дела -- это если
список слов реально очень большой, а изменения не особо частые.


Меня интересовали сначала "стандартные" предствлеия "из книжки".

Миша

Re: Word Tables

"Alex Mizrahi" <udodenko@users.sourceforge.net> wrote in message
news:fu4lbm$2340$1@ddt.demos.su...




Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.



а, ну и для полноты можно упомянуть bloom filter, если какое-то количество
ошибок не является критичным.


Наверное. Хотя это вроде просто специализированный
hash table.

Миша