uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel

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

Есть:
"мама мыла раму мама мыла мама"
Нужно:
мама - 3
мыла - 2
раму - 1
Места хватает, inplace не обязателен.
Что дешевле - отсортировать и потом сложить, или растить бинарное дерево и фильтровать через него в один проход?
Перелистал Кормена прямого ответа не нашел.
  • Вопрос задан
  • 2442 просмотра
Решения вопроса 4
begemot_sun
@begemot_sun
Программист в душе.
В случае бинарного дерева вы можете обработать бесконечный поток слов. В случае сортировки, вы должны знать весь текст стазу. Я бы остановился на бинарном дереве, ну или на чем-то среднем.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Сортировка - практически то же бинарное дерево, так что проще за один проход.
Ну или добавить корзинную сортировку, растить несколько деревьев, разделяя их по одной-двум первым буквам слова.
А может лучше и не бинарное дерево. Если алфавит заранее известен и ограничен (скажем, N символов), то в каждом узле дерева делать разделение на N ветвей, беря в качестве индекса порядковый номер символа в алфавите.
Ответ написан
Комментировать
maaGames
@maaGames
Погроммирую программы
"Дешевле" растить бинарное дерево с хэшами слов.
Ответ написан
@gurinderu
java developer
Зачем вам вообще сортировка? По моему лучше использовать Мапу, где в качестве ключа слова, в качестве значения мапы счетчик. Пройдете файл за 1 проход получите необходимую инфу, мы не будем жрать много памяти.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы