Подсчет повторяющихся слов в файле

Question

Цель: найти количество всех слов в файле. файл содержит 1000+ слов

Мой подход: используйте HashMap<String,Integer>(), чтобы сохранить и посчитать, сколько раз каждое слово появляется в файле.

Вопрос: HashMap() будет лучшим способом или лучше использовать двоичное дерево для обеспечения более быстрого поиска, поскольку в файле содержится большое количество слов?

Или есть лучший способ сделать это?

HashMap приведет к значительному увеличению объема памяти, что нежелательно.

Answer 1

Итак, вы ищете отдельные слова?

Самая эффективная структура, о которой я могу подумать, это Trie

Вот одна реализация с открытым исходным кодом: Google Code patricia-trie

Хотя я склонен согласиться с Митчем Уитом - звучит так, как будто HashMap должен работать нормально (всегда лучше избегать преждевременной оптимизации ... поэтому вы должны использовать HashMap доВы показали, что это узкое место)

Answer 2

1000 - 10000 слов очень мало.

Хэш-карта будет в порядке.

Answer 3

Я бы порекомендовал выполнить такую ​​задачу в Perl / PHP. Очень трудно убить муху из пулемета.

Answer 4

1. Если предположить, что строки не слишком длинные, подход "Три", как предполагает Майкл, был бы хорош.Узел в Trie может хранить символ и «количество» строк, которые заканчиваются этим символом.Это должно значительно снизить требования к хранилищу (опять-таки, предполагая, что строки распределены равномерно и перекрываются)

2. Предполагая, что количество не должно сохраняться при вызовах, при использовании HashMap, пусть Mapbe from Integer => Integer - где «ключ» - это хеш-код строки и значение счетчика.Это должно быть эффективным решением - с быстрым поиском и уменьшенным отпечатком памяти.

Answer 5

HashMap идеально подходит. Вам нужно хранить

• копия каждого встреченного слова
• количество для каждого

HashMap действительно не будет хранить гораздо больше!