Алгоритмический вопрос от будущего C#.NET-джуниора. С чего начать исследование?

Question

[deleted-zenshot]

Приветствую вас друзья.

Изучаю C# по книге Эндрю Троелсена. В данный момент вышел на уровень полного понимания того, о чём пишет автор. Так что чувствую в себе силы приступить к написанию своей первой программы на C#.

Придумал себе такую задачу-исследование:

Исследовать 100 английских книг, сгруппированных в 10 различных тематик.

Задача

Определить самые часто-используемые слова:

1. Во всех 100 книгах.
2. В каждой из 10 тематик.

Программу планирую написать универсальную, удобную, и так далее.

К реализации общих моментов (проектирование, отображение данных, хранение данных и т. д.) у меня особых вопросов нет. Интуитивно я понимаю, как нужно действовать. Троелсен подобные моменты хорошо разобрал.

А вот в плане реализации самого алгоритма у меня огромный ступор. Чтобы понять с чего начать, как действовать и в каком направлении двигаться, я решил поступить следующим образом:

1. Упростить задачу.
2. Задать вопросы знатокам, чтобы получить хотя бы примерный план действий.

Упрощённая задача

Подсчитать частоту вхождения каждого слова (и его вариаций) в большом текстовом документе.

Исходные данные:

Текстовый документ (книга). Количество слов в документе может доходить до нескольких сотен тысяч. Например, в книге "Pro C# 5.0 and the .NET 4.5 Framework (Andrew Troelsen)" примерно 433 000 слов.

Что нужно сделать:

Подсчитать количество вхождений в документ:

1. Каждого слова.
2. Каждой группы однокоренных слов.

Пример группы однокоренных слов:

follow
followed
follower
followers
following
followership

Вопросы знатокам:

С чего начать? Как подступиться к решению этой задачи? В каких направлениях копать?

Кто-то сможет описать хотя бы примерный алгоритм?

Answer 1

[lam0x86]

Последовательность действий такая:
1) разбиение текста на лексические единицы (в вашем случае значимыми единицами являются слова). Удобно на выходе получать IEnumerable, представляющий ленивый итератор по словам в тексте.
2) приведение слова к нормальной форме, т. е. к нижнему регистру и, опционально, к общей словоформе (например, для существительных - им. падеж, ед. число, и т.д.)
3) добавление слова в Dictionary, где ключом является само слово, а значением - счётчик:

int count;
dictionary.TryGetValue(word, out count);
dictionary[word] = count + 1;

Answer 2

[Viktor Vsk]

Зачем однокоренные слова? Вы будете считать, что follow и followership - одинаковые слова? Тогда можете взять что-нибудь готовое из fuzzy matching, например. Или, если хочется по алгоритмам - самому реализовать нахождение расстояние Левенштейна, или что-то похожее простое.

Но, как по мне, логичнее было бы сначала посторить по непосредственным словам (в книге X слово follow употребляется 123,234 раз)

И так на каждое слово. А уже потом, на основании этих данных, придумать новую задачу. Например, найти самый часто употребляемый корень.

Comments

[deleted-zenshot]

>> Но, как по мне, логичнее было бы сначала посторить по непосредственным словам (в книге X слово follow употребляется 123,234 раз)

Виктор, спасибо за ответ в целом и за это дополнение в частности. Пара уточняющих вопросов:

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

[Viktor Vsk]

1. Не надо начинать с поиска решения минимально-воможного времени выполнения
2. Не надо делать самый быстрый поиск. Получить данные по всем словам, потом сделайте, например, тот же нечеткий поиск по ним

Как столкнетесь с проблемами в производительности, тогда их и решайте (преждевременная оптимизация - это плохо). Может, ваших ресурсов (мощный процессор) и условий (всего то 10 книг по 100 000 слов) будет хватать с головой (единоразовый поиск не ограниченный по времени).

Возможно, наоборот, данных будет так много и обрабатывать так быстро, что будет играть роль не оптимизация алгоритма, а его распараллеливание.
Но это уже условия другой задачи. Производительность, безопасность, поддерживаемость, расширяемость - это все круто, но каждое слово - всего лишь задача, которая не всегда имеет место. Или не всегда в приоритете.

[deleted-zenshot]

>>1. Не надо начинать с поиска решения минимально-воможного времени выполнения
>>2. Не надо делать самый быстрый поиск. Получить данные по всем словам, потом сделайте, например, тот же нечеткий поиск по ним

А если выбирать не приходится и изначально стоит задача:
1. Сделать минимально-возможное время выполнения.
2. Поиск сделать самый быстрый из возможных.
Если задача именно такая и деваться некуда, то как бы действовал опытный программист, который с подобными задачами до этого ни разу не встречался?

[marked-one]

zenshot: Как это деваться некуда? Можно уволиться.

Абстрактные задачи бывают в ВУЗе, ну и в науке еще.

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

То есть, "опытный программист" будет исходить из того результата, который нужно получить. И первое, что он сделает, выбьет из начальства/заказчика данные для составления внятного ТЗ, например:
- на какого размера книги ориентироваться в среднем,
- будет ли необходимо алгоритму так же быстро работать с книгами большего размера или возможно послабление,
- на какие устройства рассчитано приложение (производительность, кол-во ядер, возможность менять конфигурацию устройства под приложение),
- будет ли это приложение работать однократно, или будут повторные запросы (например, если это приложение-библиотека, то можно индексировать данные о книгах при загрузке книги в библиотеку)

Не забывайте, что в большинстве случаев работодателем программиста является бизнес, а не ученые. А бизнесу важно заработать деньги, а не решить абстрактные задачи. В крайнем случае, освоить средства, но и в этом случае "самый быстрый поиск" вряд ли потребуется. Поэтому, "опытным программистом" будет выбрано то решение, которое обеспечит наилучший результат в наилучшие сроки (и премию или увеличение зарплаты себе любимому), а вовсе даже не "самый быстрый алгоритм".

Answer 3

[pro100saniok]

Автору респект. Я сам думал чтобы реализовать что-то похожое, думаю такая программа очень будет помогать тем людям у которых с английским не очень. Например ты хочешь прочитать какую то книгу, но словарный запас еще мал, выучиваешь незнакомые наиболее используемые слова(для легкости изучения их например можно додать в словарь lingualeo.com), и вперед читать=) Еще вопрос ко всем, есть ли готовое решения данной задачи? Заранее благодарен!

Answer 4

[Arthur Gurinovich]

cppstudio.com/post/1318

Answer 5

[Espleth]

Так как вы ищите конкретно слова, это не совсем поиск подстроки в строке. Вам не нужен будет оставшийся кусок слова, если оно уже не совпадает. И часть символов, такие как пробелы и знаки препинания, у вас не участвуют в сравнении.
Но вообще можете погуглить поиск подстроки в строке, алгоритмов много. Например алгоритм Кнута-Морриса-Пратта, или алгоритм Бойера-Мура.