Электронный словарь в Delphi

← →
Новичок (2010-01-24 14:47) [0]

Здравствуйте. Получил задание разработать словарь определенных терминов с описанием, с быстрым поиском. На подобие Lingvo. Сейчас словарь в документе Excel, слов около 100 тыс. Теперь у меня стоит вопрос как хранить набор слов и их описания. Для пробы я загнал словарь в документ XML, с 2-мя атрибутами, слово + описание. Затем сделал интерфейс где на форме расположен Листбокс, в который я подгружаю (объекты) слова из XML документа (средствами XMLDoc). Сама загрузка происходит очень долго.
Пожалуйста посоветуйте более быстрое решение для данной задачи, и еще словари будет необходимо шифровать. Спасибо.

← →
Юрий Зотов © (2010-01-24 15:40) [1]

Таблица БД?

Хэш_слова (Integer, первичный ключ)
Зашифрованное_слово (BLOB)
Зашифрованное_описание_слова (BLOB)

← →
@!!ex © (2010-01-24 16:01) [2]

> [1] Юрий Зотов © (24.01.10 15:40)

хэш зачем?

← →
@!!ex © (2010-01-24 16:02) [3]

Я бы в бинарном виде хранил. грузится мгновенно.

← →
Новичок (2010-01-24 16:05) [4]

из БД только работал с Ораклом и MySQL, для не большого словаря не хотелось бы поднимать сервера или запускать дополнительные службы.

> Я бы в бинарном виде хранил. грузится мгновенно.

Можно немного по подробнее, или ключевые слова для поиска. Спасибо.

← →
Юрий Зотов © (2010-01-24 16:19) [5]

> @!!ex © (24.01.10 16:01) [2]

Для ускорения поиска (по хэшу слова, а не по нему самому).

← →
@!!ex © (2010-01-24 17:26) [6]

> [5] Юрий Зотов © (24.01.10 16:19)
> Для ускорения поиска (по хэшу слова, а не по нему самому)
> .

Скорость поиска в такой штуке O(N) где N количество слов.
не лучше ли использовать дерево символов?
Памяти конечно побольше кушает, зато скорость поиска никак не зависит от количества слов.
Можно немного пожертвовать скоростью, и при всего лишь двойном потреблении памяти получить скорость опять же независяшую от количество элементов.

← →
Кто б сомневался © (2010-01-24 20:42) [7]

> Скорость поиска в такой штуке O(N) где N количество слов.

Хэши можно рассортировать по возрастанию.. Тогда найти будет нужный еще быстрее..

← →
@!!ex © (2010-01-24 20:55) [8]

> [7] Кто б сомневался © (24.01.10 20:42)

Все равно зависимость от количества.

← →
Кто б сомневался © (2010-01-24 21:01) [9]

> Все равно зависимость от количества.

Прямой зависимости уже нет.
А если сделать блоки уже отсортированных данных (допустим блок от хэша 1000 до 5000), далее делать двоичный поиск в этих блоках, тогда нужный хэш найдется очень и очень быстро..
Т.е. сначала находим блок по диапазону, в котором лежит этот хэш. А далее уже поиском двоичным..
Не думаю что это будет медленнее дерева.

← →
@!!ex © (2010-01-24 21:07) [10]

> [9] Кто б сомневался © (24.01.10 21:01)

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

← →
картман © (2010-01-25 00:51) [11]

> @!!ex © (24.01.10 17:26) [6]

> > Для ускорения поиска (по хэшу слова, а не по нему самому)
> > .
>
> Скорость поиска в такой штуке O(N) где N количество слов.
>

Скорость поиска в такой штуке О(1), вообще-то.

> @!!ex © (24.01.10 20:55) [8]
>
> > [7] Кто б сомневался © (24.01.10 20:42)
>
> Все равно зависимость от количества.

При нынешних объемах памяти, можно заполнять таблицу, да хоть на 1/10 - зависимости от N не будет.

← →
@!!ex © (2010-01-25 01:42) [12]

> [11] картман © (25.01.10 00:51)
> Скорость поиска в такой штуке О(1), вообще-то.

С какой радости О(1)???
C O(N) я не прав, потому что такая стоимость полного перебора, а у нас может и в середине быть и в начале. Вот скорость поиска по дереву константа и от количества не зависит.
А список как ни сортируй - чем больше, тем медленней.

← →
картман © (2010-01-25 01:59) [13]

> @!!ex © (25.01.10 01:42) [12]

как с какой? Слово преобразуется в хэш-значение, равное индексу в массиве.

← →
@!!ex © (2010-01-25 02:31) [14]

> [13] картман © (25.01.10 01:59)

Что за волшебный хэш такой?
Никогда не слышал о таком...

← →
картман © (2010-01-25 10:42) [15]

> @!!ex © (25.01.10 02:31) [14]

http://www.ozon.ru/context/detail/id/2640853/ - гл.7

← →
@!!ex © (2010-01-25 12:07) [16]

Волшебства не произошло... количество коллизий опять же зависит от общего количество элементов. Бесконечное расширение списка тоже не лучший вариант.
Кстати, книга так себе. бинарный поиск можно сделать вообще без сравнений.

← →
@!!ex © (2010-01-25 12:07) [17]

Ой. Опечатался. не бинарный, а по дереву

> @!!ex © (25.01.10 12:07) [16]

> количество коллизий опять же зависит от общего количество
> элементов.

количество коллизий зависит от функции хеширования и от соотношения N/Length(hash_array) - у него в словаре 100 тыс, сделай размер массива равный миллиону, как я уже писал, лишние 4 МБ особой роли нее играют.

Что за идея фикс с деревом?

> Пожалуйста посоветуйте более быстрое решение для данной
> задачи, и еще словари будет необходимо шифровать. Спасибо.
>

Префиксное дерево в собственном бинарном формате.

Хэш, он штука, конечно, хорошая, но если понадобится искать что-то по части слова, то толку от этого - ноль.

Открыл ради интереса два словаря: англо-русский Мюллера и словарь русского языка Ожегова. В первом 70000 статей, во втором 52000.
Для сегодняшних компьютеров это семечки, если, разумеется, не хранить их в виде XML и не грузить в листбокс. Без всяких хешей, примерно так же, как организуются индексы в базе банных (В+ дерево, например) и скорость поиска будет достаточно приемлемой (причем, как частичное, так и полное совпадение), в качестве бонуса - отсортированный обход.

Собственно, скорость поиска среди триллионов значение достаточно высока, что там говорить про custom-словари :)

При количестве позиций в 70000 даже тупое половинное деление в отсортированном списке найдет нужное максимум за 17 итераций. Вопрос - стоит ли городить огород со всякими наворотами?

vuk © (26.01.10 01:52) [23]

Что-то у меня под вечер туго с соображениемт. Для точного поиска потребуется максимум 17 итераций, а для инкрементного ?

Электронный словарь в Delphi Найти похожие ветки