Найти число вхождений каждого слова в документе?

Мне задали вопрос в интервью. Интервьюер сказал мне предположить, что существует функция say getNextWord(), чтобы вернуть следующее слово в данном документе. Моя задача состояла в том, чтобы создать структуру данных для реализации задачи и дать алгоритм, который строит список всех слов с их частотами.Найти число вхождений каждого слова в документе?

Будучи на фоне C++, я должен был создать multimap из string, а затем вставить в него все слова, а затем отобразить count. Мне потом сказали позже, чтобы сделать это в более родовом пути. В общем случае он имел в виду, что он не хотел, чтобы я использовал библиотечную функцию. Кроме того, я предполагаю, что multimap реализован внутренне как 2-3 дерева или около того, поэтому для решения multimap, которое будет общим, мне нужно будет также закодировать 2-3 дерева.

Хотя попытки приходят на ум, реализация одного во время собеседования для меня не о чем. Итак, я просто хотел узнать, есть ли лучшие способы его достижения? Или есть способ реализовать его плавно, используя попытки?

источник

2012-06-20 hytriutucx

Можете ли вы, пожалуйста, развернуть * generic *? – npinti

По родословной он хотел сказать, что он не хотел, чтобы я использовал библиотечную функцию.Кроме того, я предполагаю, что multimap реализован внутренне как 2-3 дерева или около того. В общем случае он хотел, чтобы я закодировал 2-3 дерева. – hytriutucx

Я бы предположил, что он хотел, чтобы вы описали структуру данных, которую вы используете, например. http://en.wikipedia.org/wiki/Hash_table, или он может захотеть, чтобы вы сделали псевдокод, а не реализацию на C++. – Kunukn

Любой алгоритм, основанный на histogram, будет иметь как исходный, так и общий характер. Идея проста: постройте гистограмму из данных. Общий интерфейс для гистограммы: Map<String,Integer>

Итерировать документ один раз (с помощью метода nextDoc()), сохраняя при этом свою гистограмму.

Лучшая реализация этого интерфейса, с точкой зрения большой нотации O -, вероятно, будет использовать trie, и в каждом узле листа - добавить счетчик появлений.

Получение фактических (word,number) пар из три будет осуществляться простой DFS на trie.

Это решение дает вам O(n * |S|) временная сложность, где | S | - средний размер строки.

Алгоритм вставки для каждого слова:
Каждый раз, когда вы добавляете новое слово: проверить, если он уже существует, если это - увеличиваем счетчик, иначе - добавить слово в словарь с значением счетчика 1.

источник

2012-06-20 08:10:55 amit

IF C++. Должен ли быть Multimap разрешать повторяющиеся ключи? – goldenmean

@goldenmean: вы не хотите повторять ключи - вы считаете их своими силами, я думаю, что это то, что интервьюер имел в виду под «более общим», – amit

Я бы попытался реализовать B-Tree (или что-то подобное), чтобы сохранить все слова. Поэтому я мог бы легко найти следующее слово, если оно уже есть, и увеличить связанный счетчик в узле. Или просто вставьте новый.

Сложность времени в этом случае будет: O(nlogn), где n - все количество слов и logn - это большой-ой для такого дерева.

источник

2012-06-20 07:18:58 gahcep

. Это не должно быть более общим, чем использование multimap. –

И также ненужным медленным с помощью O (log n). Hashmap или trie лучше и быстрее. – usamec

Может быть, общий в этом контексте означает smth other, а затем стандартную реализацию структуры данных? Потому что у нас есть естественная карта, хэш и другие в C++: std, C#: Generic. Я полагаю, интервьюер просто хотел, чтобы кандидат не слышал о знаменитой реализации алго, а о классических подходах (например, деревьях). – gahcep

Я думаю, что самым простым решением будет aa Trie. O (N) задается в этом случае (как для вставки, так и для получения счета). Просто сохраните счет в дополнительном пространстве на каждом узле.

В основном каждый узел в дереве содержит 26 ссылок на 26 возможных детей (1 для каждой буквы) + 1 счетчик (для слов, которые завершены в текущем узле) . Просто посмотрите на ссылку для графического изображения три.

источник

2012-06-20 08:34:19 OSH

Найти число вхождений каждого слова в документе?

ответ

Смежные вопросы