Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов

[Аватар]

pu4koff заразил Воспользовался его идеей и встроил сразу разборку fb2 текста и сортировку по частоте вхождения при добавлении нового слова. Прога на D7 без обработки исключений, путь к файлу в исходном тексте прошит. Эксперементировал на файле со сто тысячью слов. Основное время пошло на выделение слов из fb2. На 1-ой картинке время вместе с разборкой файла, на второй только на частотный анализ. Текст проги прилагается

[vedro-compota]

спасибо товарищи!)

[Kostia]

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

При условии что есть алгоритм который может сказать, что два слова являются одинаковыми или нет, ну или хотя бы возвращает расстояние между ними 0 - абсолютно одинаковы, 1 - полностью различны, и если расстояние < 0.1 считаем слова одинаковыми.

[Kostia]

Решил задачу в лоб для текста "война и мир" в ~3мб потребовался час. Пользовался функциями из классов которые пишу для системы по оценки знаний, там куча пред обработок, таких как удаления символов не относящихся к алфавиту, перевод к нижнему регистру, удаление лишних пробелов, разбиение всего текста на слова, все это потребовало ~пол часа xD естественно все через stl string и vector<string>, предвижу сокращение этого времени раз 5-10. Класс для статистики слов имеет метод add_word, так вот, после каждого вызова я в консоль пишу процент завершения с переводом каретки(тут прилично набегать должно). Ну и при добавлении никакой оптимизации и сортировки, тупо бегу по всему массиву, нахожу слово расстояние до которого наименьшее и оно меньше 0,1 и +1 к счетчику иначе добавляю новое слово в конец массива.

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

[_-Re@l-_]

Эм, ну вот тоже захотелось попробовать, написал прогу Испытал на книге "Гарри Поттер и Дары Смерти", вот что получил

Использовал <fstream>(т.е. потоковый ввод-вывод из файлов), и map<string,int>. Как видите, было примерно 175к слов, однако, учитывая даже то, что ввод медленный(ибо ifstream медленный, как вы знаете), программа работает мгновенно, не успеваешь даже глазом моргнуть.
Т.к. используем map, получается, что сложность у меня O(N*log(N)), где N - кол-во слов. Или я не прав?

P.S. Парсил из txt

P.P.S. pu4koff, тоже скачал Войну и Мир на 3Мб, у меня парсит около секунды Результаты почти идентичны вашим, некоторые цифра совпадают.

[Utkin]

Utkin , придётся же выполнять сортировку строк , но для этого для каждой строки (слова) надо будет какой-то ключ сформировать - напр. сумма ASSCI номеров символов . да? или как их ещё можно сортировать?

Если неоптимально и побыстрому - загнать все в TStringList - он сам на слова порежет и отсортирует. Вам останется только подсчитать слова. Не придумал как быть со знаками препинания...

[Kostia]

Оптимизировал пред обработку данных:

string clear(string s){
        int l = 0;
        for(uint i = 0; i < s.length(); i++){
            if((s[i]>='А') && (s[i]<='Я')) s[i] += ('а' - 'А');
            if((s[i]>='A') && (s[i]<='Z')) s[i] += ('a' - 'A');
            if(s[i]=='Ё') s[i] = 'ё';
            if(((s[i]<'а') || (s[i]>'я')) && (s[i]!='ё') && ((s[i]<'a') || (s[i]>'z')) && ((s[i]<'0') || (s[i]>'9')))s[i] = ' ';
            if((s[i]==' ')&&(i>0)&&(i<s.length())){
                if(s[i-1]==' ') l++;
            }
        }
        string ret;
        ret.resize(s.length()-l);
        l = 0;
        for(uint i = 0; i < s.length(); i++){
            if(s[i]==' '){
                if((s[i-1]==' ')||(i==0)||(i==s.length()-1)) continue;
            }
            ret[l++] = s[i];
        }
        return ret;
    }
    vector<string> explodeBySpace(const string &s){
        vector<string> res;
        uint i, j = 0;
        for(i = 0; i < s.length(); i++){
            if(s[i] == ' '){
                res.push_back(s.substr(j,i-j));
                j = i + 1;
            }
        }
        res.push_back(s.substr(j,i-j));
        return res;
    }

Работает практически мгновенно

До оптимизации поиска слов в массиве руки еще не дошли, только сортировку встроил и элементарное отсечение по отношению длин слов(рискованно, но пока оставлю так), итого оптимизация примерно в 6 раза, ~10 минут на "войну и мир"

вот кусок кода:

void add_word(const string &word, int num = 0){
        vector<C_Word>::iterator elem;
        double dst = 1.0;
        for(vector<C_Word>::iterator i = words.begin(); i != words.end(); i++){
            if(min(word.length(),(*i).word.length())/max(word.length(),(*i).word.length()) > 0.80){
                dst=SM.distance(word, (*i).word, true);
                if(dst <= 0.1){
                    elem = i;
                    break;
                }
            }
        }
...

[_-Re@l-_]

Kostia

 if((s[i]>='А') && (s[i]<='Я')) s[i] += ('а' - 'А');
            if((s[i]>='A') && (s[i]<='Z')) s[i] += ('a' - 'A');
            if(s[i]=='Ё') s[i] = 'ё';

Хм... Не проще ли так ?

#include <cctype>
....
s[i] = tolower(s[i]);
....

[Utkin]

Я все про второй вариант . В C# метод Split позволяет использовать группу разделителей, то есть можно забить и пробел и точки с запятыми. Ну и уже потом сортировать массив полученных слов...

[Kostia]

Сообщение от _-Re@l-_

Kostia

 if((s[i]>='А') && (s[i]<='Я')) s[i] += ('а' - 'А');
            if((s[i]>='A') && (s[i]<='Z')) s[i] += ('a' - 'A');
            if(s[i]=='Ё') s[i] = 'ё';

Хм... Не проще ли так ?

#include <cctype>
....
s[i] = tolower(s[i]);
....

Замедляет предобработку примерно в 2-3 раза по ощущениям

Я все про второй вариант . В C# метод Split позволяет использовать группу разделителей, то есть можно забить и пробел и точки с запятыми. Ну и уже потом сортировать массив полученных слов...

Запихать в Split (,.@#$%^&*?:%;№"! ...)? +Как то проконтролировать всякий мусор в виде не читаемых символов и пр. Легче создать свой алфавит и игнорить (превращать в пробелы) мусор.