Возникла проблема. Пишу прогу, для которой требуется словарь в котором в каждой словарной статье есть: слово, его транскрипция, и 3-4 варианта перевода. Каковы принципы организации подобных словарей? Как можно организовать индексацию? Может быть кто-нибудь знает, как это сделано в Lingvo или в MultiLex? Зарание спасибо.
Для удобства поиска разбить весь словарь на словари по алфавиту, разделить сами слова и транскрипцию с переводом. Получится тройная индексация: 1) алфавит, индекс индексов; 2) слова; 3)перевод и транскрипция. алфавит --> cлова --> перевод и трн. Как это сделать програмно думаю понятно.
Для индексации лучше всего использовать хэширование, если словарь не очень большой, и есть возможность хранить его целиком в памяти. На тот случай, если словарь хранится в дисковом файле, существуют B-trees или расширяемое хэширование. Например, один из вариантов B-деревьев реализован в NTFS для хранения каталогов. B-деревья и расширяемое хэширование неплохо описаны у Роберта Седжвика (книжка "Фундаментальные алгоритмы на Си"). По B-деревьям могу еще пару ссылок подкинуть, если надо. _Raven_: AFAIK, в таких словарях используют обычную хэш-таблицу, и она загружается в память в начале работы программы. В энциклопедии "Кирилла и Мефодия" точно используют ее, так как при загрузке программа сильно тормозит . И немудрено, учитывая размер словника. Требования к качеству хэш-функции у тебя не такие жесткие, как в компиляторах, поэтому достаточно чего-то вроде (беззастенчиво позаимствовано из Седжвика): Код (Text): int hashU(char *v, int M) { int h, a = 31415, b = 27183; for(h = 0; *v != '\0'; v++) h = (a * b + *v) % M, a = a * b % (M - 1); return h; } Магические числа a и b генерируют псевдослучайную последовательность множителей. В "Книге Дракона" (Ахо, Сети, Ульман. "Компиляторы: принципы, технологии и инструменты") приведен тест нескольких хэш-функций, эта показала неплохие результаты. Со связными списками не мучайся (их сложно сохранять в файл), возьми алгоритм псевдослучайной проверки для разрешения коллизий. Почитать о нем можно в "Готовых алгоритмах на Visual Basic" Рода Стивенса. Книжка хорошая, хоть и про басик.
"псевдослучайная последовательнасть множителей", зачем это еще такой изврат объясните, так как мне самому нужно будет создавать словари Моя идея заключаться в том что в файле словаря складируються сначала индесы алфавита - указатели к первому указателю на слово буквы, допустим dword, потом указатели на слова и перевод: qword, один dword на слово - другой на перевод, между буквами ставиться нулевой qword, дальше слова раделенные нулем и после преревод и.т.п. да, забыл слова должны быть отсортированы.
zzzyab Я почти не знаю теории хэширования. Но догадываюсь. При проходе хэшфункции по строке разной длины мы получаем, случайную цыфру, почти не повторяющуюся для различных строк. Дальше делается двусвязный список из хэший и индексов, сортируется по хеш и бинарным поиском за 16/32 шага находим нужное слово. А твое предложение не подходит, так как ты таким способом ты сможешь искать только по первой буквы. Иначе тебе продеться заводить для каждой следующий буквы свой индекс. Что влечет увеличение числа индексов, и скорость падает порядка N^2, где N= число букв в степени максимальной длины слова. Что равносильно поиску без индексев. ps SDragon Я думаю, что в твоем алгоритме ошибка, там должна быть зависемость h от h на предыдущем шаге, но я могу ошибаться.
SDragon, буду очень признателен за ссылки по B-деревьям. Нет ли электронного варианта книги Роберта Седжвика? В моём случае, словарь будет очень большой, соответственно, хранится в дисковом файле. Есть ли какая-либо принципиальная разница в реализации хранения В-дерева в NTFS и в FAT?
Число базовых инедксов соответсвует числу букв (33 для русского языка) а количество индексов слов = количеству самих слов. Например искомое слово вводиться в эдит контрол, при вводе буквы программа отсчитывает индекс по ее номеру, индекс у меня указатель, по указателю присходит переход на словарь, и прога в каком нибуть виде отображает все слова по указателю до двух нулей. При вводе второй буквы прога выполняет поиск все по тому же указателю и выводит слова где эти сочитания букв есть и запускает счечик на нули, который сохранатся при первом совпадении и потом при первом несовпадении по принципу xor. При вводе следующей буквы указатель увеличеветься на значение совпадения умноженое на размер индекса (4 или 8), а счетчик выставляеться на значение несовпадения минус значение совпадения (типа сужение круга поиска) - повтор продседуры пока не найдено слово, если не найдено - сброс и все по новой. Если слово нашлось то чтобы отобразить перевод программа прибавлет к указателю значение счетчика умноженое на 4 или 8 в зависимости от размеров индекса и по найденому указателю выводит перевод. Из поста Pavia выходить что слово можно закодировать в уникальное число, эта идея вобщем понятна. Но как этим методом искать не все слово а только его часть, например как в Рута-Плай. Если слово это одно число, то часть слова это уже совсем другое число, получаеться как раз и N комбинаций.
Ссылки по B-trees: http://sky.fit.qut.edu.au/~maire/baobab/baobab.html http://cis.stvincent.edu/swd/btree/btree.html http://www.bluerwhite.org/btree http://www.semaphorecorp.com/btp/btp.html По хэшированию: http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/hash_tables.html http://users.actcom.co.il/~choo/lupg/project-ideas/hash-tables.html http://www.sparknotes.com/cs/searching/hashtables/section1.html http://ww3.algorithmdesign.net/handouts/HashTables.pdf Pavia: Спасибо! Правильный вариант: Код (Text): h = (a * [b]h[/b] + *v) % M, a = a * b % (M - 1); Я провел небольшое исследование; оказалось, что можно обойтись без этого изврата . Достаточно простой модульной хэш-функции типа: Код (Text): int hash(char *v, int M) { int h = 0, a = 65537; // Множитель a и размер таблицы M должны быть взаимно простыми // числами. Удобнее всего взять простое a, например, 65537 while(*v) h = (a * h + *v) % M, v++; return h; } Дело в том, что хэш-функция должна давать равновероятные значения для всех элементов таблицы. А распределение букв по частоте неравномерное, например, буква E встречается во много раз чаще, чем Q или X (вероятность E - 0,13, вероятность Q и X около 0,01). Предположим, мы будем использовать в качестве хэша код буквы (или нескольких букв из слова). Слов, содержащих E, много, и в таблице они все собьются "в одну кучу" около кода буквы E. А ячейки, соответствующие Q и X, будут почти пустыми. Согласно Седжвику, функция с псевдослучайными множителями является теоретически идеальной - дает абсолютно равномерное распределение. Но оказалось, что на практике достаточно простой модульной функции. Во вложении приведен Excel'евский макрос, проверяющий обе функции на списке слов из Wiktionary (около 500 слов, которые должны быть в каждом словаре Wiktionary). Для псевдослучайных коэффициентов (функция hashU) получилось 109 коллизий, для модульного хэша (hash) - 113. Практически никакой разницы, по крайней мере для слов естественного языка. В файле есть также критерий качества - это из "Книги Дракона". Чем он ближе к единице, тем лучше. Если есть еще вопросы, задавайте . _1550828426__Hashing.7z
_Raven_ В FAT-e нет B-Tree, там другого плана дерево. Организуешь структуру. PTree=^TTree; TTree= record c:char; Символ p:pointer; Указатель на данные l,r:PTree; Указатель на левый и правые ветви end; Строится такое дерево.По правой ветви идет изменение длины слова, по левой изменение конечный буквы. Код (Text): (О) \ (Н) / \ (Р) (Eol) / (А) поиск осуществляется обходом в глубину. Хранить лучше всего в виде массива, и в качестве перехода между элементами использовать индекс элемента массива. zzzyab Долго сооброжал о чем ты толкуешь и наконец понял. Но твой алгоритм, очень медленен. Тебе по любому предеться пробежаться L раз по N элементам. Где L длина слова, а N~(Число слов)/33.
_Raven_: В FAT вообще нет B-дерева, там в каталогах лежит неупорядоченный список файлов. Про B-деревья в NTFS можно почитать здесь: http://linux-ntfs.sourceforge.net/ntfs/concepts/tree/ Увы, нет. Pavia Гораздо проще. Идея хэширования в том, что мы можем написать a[123], но не можем a["abc"]. В качестве индекса массива в Си нельзя использовать строки. А хотелось бы! Вычислительная сложность поиска порядка O(1) -- то есть мы просто тыкнули в ячейку памяти и извлекли из нее значение. Очень заманчиво . Как этого добиться? Создается хэш-таблица: char* HashTable[M]; // Таблица указателей на строки В ней лежат все слова, при необходимости можно сделать указатель на структуру и запихнуть в структуру само слово, его транскрипцию, переводы и т.п. Индексом в этой таблице является значение хэш-функции. То есть строку "abc" мы пихаем в хэш-функцию, она выдает нам какое-то число, и мы используем это число в качестве индекса, то есть пишем HashTable[HashFunc("abc")]. Но это только базовая идея. На самом деле хэш-функция не способна выдать для всех строк неповторяющиеся значения, поэтому возникают коллизии... Дальше иди по ссылкам, читай и просвещайся . zzzyab Тогда нужно не хэширование, а деревья бинарного поиска или в случае с большими файлами -- B-деревья. В них довольно легко выбрать слова, начинающиеся с определенной буквы.
