Как посчитать словарь текста?

Question

[uvelichitel]

Есть:
"мама мыла раму мама мыла мама"
Нужно:
мама - 3
мыла - 2
раму - 1
Места хватает, inplace не обязателен.
Что дешевле - отсортировать и потом сложить, или растить бинарное дерево и фильтровать через него в один проход?
Перелистал Кормена прямого ответа не нашел.

Answer 1

[Сергей]

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

Comments

[uvelichitel]

Текст конечен. Реализацию буду писать на Golang. Можете уточнить ответ до да-да, нет-нет?

[uvelichitel]

uvelichitel: Реализацию буду писать на Golang. То есть у меня в инструментарии еще будет ассоциативный массив.

[Сергей]

Ну вот давайте подумаем, что проще: сделать в памяти дерево на 5 Мбайт, либо обработать гору текста размером 14 Гб ?
Я бы выбрал потоковое решение, и именно реализация дерева(ассоциативного массива) дает вам в этом выигрыш.

Answer 2

[Rsa97]

Сортировка - практически то же бинарное дерево, так что проще за один проход.
Ну или добавить корзинную сортировку, растить несколько деревьев, разделяя их по одной-двум первым буквам слова.
А может лучше и не бинарное дерево. Если алфавит заранее известен и ограничен (скажем, N символов), то в каждом узле дерева делать разделение на N ветвей, беря в качестве индекса порядковый номер символа в алфавите.

Answer 3

[maaGames]

"Дешевле" растить бинарное дерево с хэшами слов.

Comments

[uvelichitel]

Кажется хэширование не бесплатно, разве что фильтр Блума подешевле. Но это все не overingeneering вы считаете? Можно оценить на каком размере текста и словаря это окупается? Ссылки на оценку будет достаточно для меня.

[maaGames]

uvelichitel: "дешевле" только по использованию памяти и времени поиска в дереве. Хэш - сравнительно небольшое бинарное число (4-8 байт). Слова в юникоде будут иметь гораздо больший объём и сравниваться будут посимвольно. Т.е. чем больше длина слов и, чем больше вообще слов (больше высота дерева), тем больше будет выгода от хэширования.
Не знаком со спецификой golang, может на нём и нет разницы, но на настоящих языках программирования с числами работа происходит существенно быстрее, чем со строками.

[uvelichitel]

maagames.ru: Вы меня не поняли. Хэш дорог в производстве, его же нужно считать. Памяти в условиях моей задачи достаточно.

[maaGames]

uvelichitel: Я понял. Дороговизна хэш-функции зависит от того, что за хэш функция. Можно хоть CRC считать, хоть банально ксорить буквы (но не надо)...
Сортированный массив имеет смысл делать только если заранее известно количество разных слов (а это не известно). Так что строй дерево и не парься, тем более памяти полно.

[uvelichitel]

maagames.ru: Идея с хэшем интересна. Подскажите легкую функцию для текста 10000 слов, словаря 500 слов, слова 10 юникод рун и я отмечу ответ решением.))))

[maaGames]

uvelichitel: Я не знаю возможностей golang. Если разруливать коллизии (про несколько деревьев уже писали в первом ответе), то достаточно ксорить все символы строки. Если коллизии постараться избежать, то md5, но там много битовых операций. Если golang умеет в деление больших чисел, то можно остаток от деления на простое число считать. Ради словаря в 500 слов нет смысла заморачиваться и можно обычное дерево строить (8 сравнений строк в среднем потребуется). Даже ради 10000 слов особого смысла нет (всего 14 сравнений потребуется).