|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.05.2012, 17:22 | #11 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
pu4koff заразил Воспользовался его идеей и встроил сразу разборку fb2 текста и сортировку по частоте вхождения при добавлении нового слова. Прога на D7 без обработки исключений, путь к файлу в исходном тексте прошит. Эксперементировал на файле со сто тысячью слов. Основное время пошло на выделение слов из fb2. На 1-ой картинке время вместе с разборкой файла, на второй только на частотный анализ. Текст проги прилагается
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
29.05.2012, 22:20 | #13 |
Участник клуба
Регистрация: 21.11.2007
Сообщений: 1,690
|
Извиняюсь что встреваю в тему. Интересно было бы узнать мнения по возможности оптимизации данного алгоритма, если слова являются не четкими наборами символов. Например слова "переменная" и "переменая" являются одинаковыми, а также слова в разных словоформах тоже являются одним словом, например "игра" и "играя".
При условии что есть алгоритм который может сказать, что два слова являются одинаковыми или нет, ну или хотя бы возвращает расстояние между ними 0 - абсолютно одинаковы, 1 - полностью различны, и если расстояние < 0.1 считаем слова одинаковыми. |
30.05.2012, 01:08 | #14 |
Участник клуба
Регистрация: 21.11.2007
Сообщений: 1,690
|
Решил задачу в лоб для текста "война и мир" в ~3мб потребовался час. Пользовался функциями из классов которые пишу для системы по оценки знаний, там куча пред обработок, таких как удаления символов не относящихся к алфавиту, перевод к нижнему регистру, удаление лишних пробелов, разбиение всего текста на слова, все это потребовало ~пол часа xD естественно все через stl string и vector<string>, предвижу сокращение этого времени раз 5-10. Класс для статистики слов имеет метод add_word, так вот, после каждого вызова я в консоль пишу процент завершения с переводом каретки(тут прилично набегать должно). Ну и при добавлении никакой оптимизации и сортировки, тупо бегу по всему массиву, нахожу слово расстояние до которого наименьшее и оно меньше 0,1 и +1 к счетчику иначе добавляю новое слово в конец массива.
Предвижу следующую оптимизацию. Ее можно тоже представить в виде дерева, но мне проще представляется в виде колец. В центре находится некоторое слово, все остальные слова расположены на некотором расстоянии до него, если выполнить разбиения всего круга на несколько областей(колец), то мы сможем сократить поиск, если сначала выполнить расчет расстояния до центрального слова, а последующий поиск выполнять уже внутри кольца в которое попало слово. Естественно все эти кольца можно разбивать на под кольца и так на несколько уровней вглубь. Подобрать центральное слово таким образом, чтобы вероятность попадания слова в одно из колец была одинаковой (равномерное распределение), не представляю возможным, но есть возможно подобрать такое слово чтобы получилась гауссово распределение (догадка что оно будет таковым). Таким словом, или набором символов можно считать обобщенную медиану, полученную из большого множества различных слов. Последний раз редактировалось Kostia; 30.05.2012 в 01:11. |
30.05.2012, 09:38 | #15 |
C++, Java
Старожил
Регистрация: 10.04.2010
Сообщений: 2,665
|
Эм, ну вот тоже захотелось попробовать, написал прогу Испытал на книге "Гарри Поттер и Дары Смерти", вот что получил
Использовал <fstream>(т.е. потоковый ввод-вывод из файлов), и map<string,int>. Как видите, было примерно 175к слов, однако, учитывая даже то, что ввод медленный(ибо ifstream медленный, как вы знаете), программа работает мгновенно, не успеваешь даже глазом моргнуть. Т.к. используем map, получается, что сложность у меня O(N*log(N)), где N - кол-во слов. Или я не прав? P.S. Парсил из txt P.P.S. pu4koff, тоже скачал Войну и Мир на 3Мб, у меня парсит около секунды Результаты почти идентичны вашим, некоторые цифра совпадают. Последний раз редактировалось _-Re@l-_; 30.05.2012 в 10:04. |
30.05.2012, 11:41 | #16 | |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
|
30.05.2012, 12:50 | #17 |
Участник клуба
Регистрация: 21.11.2007
Сообщений: 1,690
|
Оптимизировал пред обработку данных:
Код:
До оптимизации поиска слов в массиве руки еще не дошли, только сортировку встроил и элементарное отсечение по отношению длин слов(рискованно, но пока оставлю так), итого оптимизация примерно в 6 раза, ~10 минут на "войну и мир" вот кусок кода: Код:
|
30.05.2012, 13:33 | #18 |
C++, Java
Старожил
Регистрация: 10.04.2010
Сообщений: 2,665
|
Kostia
Код:
Код:
|
30.05.2012, 13:43 | #19 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Я все про второй вариант . В C# метод Split позволяет использовать группу разделителей, то есть можно забить и пробел и точки с запятыми. Ну и уже потом сортировать массив полученных слов...
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
30.05.2012, 21:01 | #20 | ||
Участник клуба
Регистрация: 21.11.2007
Сообщений: 1,690
|
Цитата:
Цитата:
Последний раз редактировалось Kostia; 30.05.2012 в 21:17. |
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
из текстового файл получить 5 наиболее часто встречающихся слов и число их появлений (на Delphi) | sifa | Помощь студентам | 5 | 09.01.2012 18:34 |
в тексте слова, содержащие ровно одну из 10 наиболее часто встречающихся букв | yaroslav_bondarev | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 16.12.2011 10:11 |
дан текст, написать код, нахождения 10 наиболее часто встречающихся букв | yaroslav_bondarev | Паскаль, Turbo Pascal, PascalABC.NET | 9 | 14.12.2011 22:08 |
Получить массив из элементов, встречающихся в исходном массиве ровно один раз без повторений | Shikarmo4000 | Помощь студентам | 0 | 25.05.2010 01:27 |
Найти (в процентах) частоту появления каждого из m наиболее часто встречающихся элементов | sk1p | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 26.09.2008 23:57 |