Зная, что в английском словаре около 200 тысяч слов, а в алфавите 26 букв или около того.
Каков размер префиксного дерева (trie), содержащего все английские слова?
comment
Ваша оценка занижена. Согласно Оксфордским словарям существует минимум четверть миллиона английских слов, и это не считая технических слов, которые не отслеживаются словарем.
- person Jim Mischel schedule 05.03.2014
Ответы (3)
В этой статье автор построил пример английского слов из файла длиной 935 015 байт. Для этого потребовалось четверть миллиона узлов. Он заявляет о степени сжатия примерно 73%, что довольно близко к тому, что я помню из своей работы с такими структурами данных.
Обратите внимание, что его реализация тратит много памяти, сохраняя массив из 26 дочерних указателей для каждого узла. Гораздо менее дорогая реализация будет поддерживать только те указатели, которые ей нужны, упорядоченные по частоте использования. Например, хранить 26 указателей дочерних узлов для буквы q в слове — это безумие, учитывая, что крайне маловероятно, что символ после q будет чем-то другим, кроме u.
Последовательный поиск занял бы немного больше времени, чем прямая индексация массива, но позволил бы значительно сэкономить память. А экономия памяти может привести к гораздо меньшему количеству промахов в кэше, что с лихвой компенсирует увеличение стоимости линейного поиска.
Если вы хотите сэкономить еще больше места, вы можете создать направленный ациклический граф слов, в котором также используются общие окончания и некоторые другие оптимизации. Например, вы можете сжать висячие окончания в один узел.
person
Jim Mischel
schedule
05.03.2014
При использовании простого дерева префиксов требуемое пространство должно быть O(N*C), где C — среднее количество символов в слове, а N — количество слов. Это связано с тем, что в худшем случае Trie будет хранить каждый символ в каждом слове. Таким образом, справедливой оценкой будет около 1 миллиона сохраненных символов или около 1 МБ.
person
Nuclearman
schedule
04.03.2014
У вас есть ссылки на это? Пример из 600 000 английских слов будет хранить значительно меньше, чем 600 000 узлов. Наверняка нет, я знаю магазины c, ca и cat для слова cat. Я думаю, вам нужно прочитать, что такое попытка и как она хранится. en.wikipedia.org/wiki/Trie
- person Jim Mischel; 05.03.2014
Действительно, я имел в виду более сложную структуру данных, используемую для поиска подстроки, основанную на Trie. Хотя, если подумать, это тоже может быть O(NC). В этом случае это только O(NC), где C — среднее количество символов, и это много.
- person Nuclearman; 05.03.2014
Да. (N*C) — наихудший случай, который возможен только при отсутствии общих префиксов.
- person Jim Mischel; 05.03.2014
Я сказал, что попытка из 600 000 английских слов будет хранить менее 600 000 узлов. Я имел в виду, что слова состоят из 600 000 символов.
- person Jim Mischel; 05.03.2014
Учитывая, что среднее количество символов постоянно, количество символов и слов равно O(N). Так что я знал, что вы имели в виду, даже если я не уловил ошибку. Я дважды просмотрел почти 600 000, просмотрел ваш ответ и перешел по ссылке, которую вы дали, чтобы просмотреть его более подробно.
- person Nuclearman; 05.03.2014
Учитывая эту статью, в настоящее время в английском языке goo.gl/tlgxTW используется менее 200 тысяч слов.
- person Raul; 06.03.2014
В следующей реализации goo.gl/J5i2br количество ссылок в дереве находится между CN и CNk, где k — средняя длина ключа. У каждого ключа в дереве есть узел, содержащий связанное с ним значение, которое также имеет L ссылок, поэтому количество ссылок не менее LN. Если первые символы всех ключей различны, то существует узел с L ссылками для каждого символа ключа, поэтому количество ссылок равно L, умноженному на общее количество символов ключа, или LNk .
- person Raul; 06.03.2014
Wolfram alpha говорит, что средняя длина слова будет 5,1 символа http://www.wolframalpha.com/input/?i=average+english+word+length
Если L=26, количество букв в алфавите и K=5,1 средняя длина английского слова.
=> Я ожидаю, что сложность пространства будет где-то около O (L ^ K) (L в степени K)
Я полагаю, что реализация на реальном языке может отличаться.
person
Raul
schedule
04.03.2014
Ваша оценка кажется необоснованной. L^K — это количество всех строк длины K с алфавитом из L символов, т. е. единственное релевантное число, которое он может оценить, — это количество слов, но это уже дано, это не количество, которое мы пытаемся найти. Более того, это неправильно даже для этой цели, как в теории (он считает все возможные строки, которые имеют ту же длину, что и среднее английское слово, но большинство из них не являются английскими словами, и многие английские слова имеют разную длину), так и на практике ( это дает около 8,8 млрд вместо 200 тысяч).
- person ; 05.03.2014
В дополнение к возражениям @delnan, число
L^K не предполагает общих префиксов. Весь смысл дерева префиксов в том, чтобы использовать общие префиксы. Быстрый поиск показывает эмпирические результаты в диапазоне от (N*K)/4 до (N*K)/3 узлов, где N — количество слов, а K — средняя длина слов.
- person Jim Mischel; 05.03.2014
