Подсчет частоты слов в тексте

[Alexander]

Добрый день!

Если кто сталкивался с подобной задачей, подскажите, где я допускаю ошибку:

-- Необходимо подсчитать сколько раз слово встречается в списке и убрать дубликаты. Использую контейнер QHash<QString, int> для быстрой обработки и записываю финальные Key и Value в разные списки. Но функция выдает только список уникальных слов (Key) в конце и не выводит частоты. Кроме того, функция обрабатывает текст размером 100 Кб ОЧЕНЬ медленно, может есть какие-то варианты ее оптимизировать?

Вот такой код:

Код:

// Переменная Token типа QStringList хранит список всех слов из текста

void Tokenizer::WordCount ()
{
    QHash<QString, int> countWord;

    for (int i=0; i<Token.size(); ++i)
    {
        foreach (QString word, Token)
        countWord[word]+=1;
    }
    for (QHash<QString, int>::iterator iter=countWord.begin(); iter!=countWord.end(); ++iter)
    {
        QStringList Key;  // переменная, чтобы вывести в виде списка
        QStringList Value; // -/-/-/
        QTextStream out; // 'конвертирование' ...
        out<<iter.value(); // int ...
        QString temp;      // в string ...
        out>>temp;        //
        Value.append(temp);
        Key.append(iter.key());
        ui->Token_list->addItems(Key);
        ui->Split_list->addItems(Value);
    }
}

[SABROG]

Читай внимательней документацию. Мало того, что у тебя ключи могу быть одинаковыми, так ты еще в памяти через оператор [word] плодишь кучу копий. Создание QTextStream в цикле и использование его для преобразования intToString  вообще убивает. foreach() незаметно создает копию контейнера, тебе оно надо? iter!=countWord.end() - тут каждый раз создается новый объект итератор, что также замедляет работу приложения, вызовы конструктора и деструктора на каждом цикле. Вынеси его перед циклом один раз. ui->Token_list->addItems(Key); - опять же, зачем в цикле? Заполни до конца QStringList и добавляй после цикла. Чтобы найти "узкие" места в программе используй профайлер, gprof например.

[Alexander]

Может быть тут сказывается тот факт, что за с++ я сел меньше 3-х месяцев назад, но то, что дется в Qt Assistant по поводу ассоциативных контейнеров не проливает свет на то, как правильно задать уникальные ключи и накапливать частоту в int.
Что касается преобразования intToString, то единственный метод, который я нашел - itoa - как я понимаю не универсален.
Опять же итератор iter!=countWord.end() во всех примерах, которые мне встретились, стоит в цикле, и что означает вынести его перед циклом мне не совсем ясно.

[Vass]

Статический метод QString::number(); преобразует число в строку.

[SABROG]

как правильно задать уникальные ключи и накапливать частоту в int.

Тут я ошибся, у тебя QString выступает в роли ключа.

Что касается преобразования intToString, то единственный метод, который я нашел - itoa - как я понимаю не универсален.

QString::number();
QString("%1").arg(int);
QString::setNum();

Опять же итератор iter!=countWord.end() во всех примерах, которые мне встретились, стоит в цикле, и что означает вынести его перед циклом мне не совсем ясно.

Код

C++ (Qt)
QHash<QString, int>::iterator end = countWord.end();
for (QHash<QString, int>::iterator iter = countWord.begin(); iter != end; ++iter)
 

Примеры бывают и не оптимизированными...

[Alexander]

как правильно задать уникальные ключи и накапливать частоту в int.

Тут я ошибся, у тебя QString выступает в роли ключа.

Что-то я теперь запутался. Ключем должно выступать слово, а значением - накапливаемое количество?
т.е. вариант

Код

C++ (Qt)
QHash<QString, int>

Если метод foreach () не подходит, то значит надо проходить по списку итераторами сравнивая подстроки? И соответственно на месте оператора [word] нужно использовать int?

[SABROG]

Что-то я теперь запутался. Ключем должно выступать слово, а значением - накапливаемое количество?
т.е. вариант

Код

C++ (Qt)
QHash<QString, int>

QHash<Key, T> - да, первое ключ (key), второе значение (value)

Если метод foreach () не подходит, то значит надо проходить по списку итераторами сравнивая подстроки? И соответственно на месте оператора [word] нужно использовать int?

Код

C++ (Qt)
    QStringList::const_iterator constEnd = Token.constEnd();
    for (QStringList::const_iterator i = Token.constBegin(); constEnd != Token.constEnd(); ++i)
        countWord[*i] += 1;
 

При складывании значения выполняется неявное копирование, так как значение сначала читается, но тут по другому и не сделать, через at() например, получится тоже самое копирование.

[Igors]

-- Необходимо подсчитать сколько раз слово встречается в списке и убрать дубликаты. Использую контейнер QHash<QString, int> для быстрой обработки и записываю финальные Key и Value в разные списки. Но функция выдает только список уникальных слов (Key) в конце и не выводит частоты. Кроме того, функция обрабатывает текст размером 100 Кб ОЧЕНЬ медленно, может есть какие-то варианты ее оптимизировать?

Оператор [] для QHash на примере:

Код:

 for (int i=0; i<Token.size(); ++i)
        ++countWord[Token[ i ]];

Оператор возвращает ссылку на значение (у Вас int), его можно прямо менять. Если ключа (Token[ i ]) не было в QHash - он будет вставлен (с default значением, 0 для int). Для подсчетов числа вхождений - то, что надо

Для печати вхождений Вы правильно "итерировались" по countWord но чего ж QDataStream объявлять в цикле? А если надо добавить к спискам, то проще countWord.keys() и countWord.values() вместо цикла.

Удаление дубликатов также легко и приятно

Код:

 QStringList outLst;
 for (int i=0; i<Token.size(); ++i)
        if (countWord[Token[ i ]]  < 2)
          outLst.push_back(Token[ i ]]);  

Здесь никаких вставок в countWord не произойдет, т.к. все ключи созданы при подсчете вхождений

Edit: может если 2 и более вхождения - то надо убрать все кроме первого? Тогда тоже легко, напр

Код:

 QStringList outLst;
 for (int i=0; i<Token.size(); ++i) {
      int & val = countWord[Token[ i ]];
       if (val < 0) continue;                         // второе или след вхождение, пропускаем
       outLst.push_back(Token[ i ]]);
       if (val > 1) val = -val;                        // отмечаем
 }  

[Alexander]

Спасибо за помощь! Сейчас приложу это все к программе.

Что касается опять же оптимизации, то можно ли вариант с вынесенным перед циклом итератором constEnd = Token.constEnd(); изменить так:

Код:

QStringList::const_iterator constEnd = Token.constEnd();
QStringList::const_iterator i = Token.constBegin(); // т.е. вынести перед циклом также и итератор начала?
    for (; constEnd != Token.constEnd(); ++i)
        countWord[*i] += 1;

Будет ли это иметь какой-то эффект?

[Alexander]

И еще вопрос...

По задумке значения Key и Value выводятся в два QListWidget'а. Можно ли синхронизировать/связать между собой эти списки, чтобы скажем при прокрутке списка слов прокручивался и список частот?
И как можно отсортировать QHash по ключу, как это делает QMap?

[SABROG]

Что касается опять же оптимизации, то можно ли вариант с вынесенным перед циклом итератором constEnd = Token.constEnd(); изменить так

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

По задумке значения Key и Value выводятся в два QListWidget'а. Можно ли синхронизировать/связать между собой эти списки, чтобы скажем при прокрутке списка слов прокручивался и список частот?

Да, нужно взять указатель на QScrollBar: QListWidget::verticalScrollBar() и подключить сигнал QAbstractSlider::valueChanged() на слот QAbstractSlider::setValue() указателя взятого со второго QListWidget'a.

И как можно отсортировать QHash по ключу, как это делает QMap?

Скопировать QHash в QMap.

Igors, проще было бы человеку ссылку дать http://www.prog.org.ru/topic_10606_30.html

P.S.: похоже студенты из одного универа. 

[Alexander]

P.S.: похоже студенты из одного универа.

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

Да, нужно взять указатель на QScrollBar: QListWidget::verticalScrollBar() и подключить сигнал QAbstractSlider::valueChanged() на слот QAbstractSlider::setValue() указателя взятого со второго QListWidget'a.

Это нужно прописывать в коде в ручную или можно воспользоваться редактором слотов и сигналов в qt designer? Просто щас быстро гланул, не нашел там таких сигналов и слотов этих виджетов...

Хотел перенести объявление QHash<QString, int> countWord в файл .h класса, при сборке выдает сообщение 'field "countWord" has incomplete type'. Добавляю #include <QHash> - компилит нормально. Хотя там же в заголовочном файле объявляю скажем ту же самую QStringList Token без инклуда соответствующего класса - не ругается. Почему так происходит?

[SABROG]

Это нужно прописывать в коде в ручную или можно воспользоваться редактором слотов и сигналов в qt designer? Просто щас быстро гланул, не нашел там таких сигналов и слотов этих виджетов...

Видимо потому, что "быстро"

Код

C++ (Qt)
QObject::connect(listWidget1->verticalScrollBar(), SIGNAL(valueChanged(int)), listWidget2->verticalScrollBar(), SLOT(setValue(int)));
 

Хотел перенести объявление QHash<QString, int> countWord в файл .h класса, при сборке выдает сообщение 'field "countWord" has incomplete type'. Добавляю #include <QHash> - компилит нормально. Хотя там же в заголовочном файле объявляю скажем ту же самую QStringList Token без инклуда соответствующего класса - не ругается. Почему так происходит?

QStringList это классы QList и QString, если есть подключение этих заголовков то тогда понятно, если нету, то могу сказать, что косвенно Qt может какие-то заголовки подключать внутри себя. Советую под любой внешний класс подключать соответствующий заголовок. Любители компилятора майкрософт этого не делают, а потом у других людей, которые пытаются собрать программы через gcc вываливаются ошиби, так как gnu complier более строг к стандарту чем msvc. Сами тролли уже грешили пару раз с этим. Выпустят чего-нибудь, а оно не собирается. Потом приходится им багрепорт писать, чтобы инклуд добавили.