Частотный словарь как сделать

Добавил пользователь Евгений Кузнецов
Обновлено: 19.09.2024

Частотный словарь одной книги называется конкорданс.

Сделать простейший конкорданс очень просто. Для этого можно воспользоваться как онлайн сервисами, так и устанавливаемыми программами, благо есть множество бесплатных разработок.

На этой странице перечислено довольно много оффлайн и онлайн предложений для создания конкордансов. На этой странице также кратко обозреваются некоторые наиболее популярные программы, а ещё даётся пример кода на языке Python, который можно адаптировать под свои нужды. Я сама пользуюсь программой AntConc (есть в обоих списках) или самодельными скриптами, но никому своего мнения не навязываю.

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

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

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

Целью данной работы является разработка алгоритмов для построения частотных словарей. При выборе методики решения были рассмотрены два способа представления данных: двоичные деревья и хэш-таблица [2].

Хеш-таблица — структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары ключ-значение и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Двоичное дерево — древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

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

Код созданной структуры выглядит следующим образом:

В качестве хеш-функции была выбрана Djb, потому что это простая и быстрая хэш-функция общего назначения. Так же из достоинств функции можно отметить хорошее распределение и простоту конструкции. Данная функция разработанная профессором Дэниэлом Берштейном, американским математиком и программистом. Она не является криптографически-безопасной, возвращает 32-разрядное беззнаковое число в качестве хеш-суммы. Код используемой хеш-функции выглядит следующим образом (

Похожие статьи

Использование алгоритмов нечеткого поиска при решении.

Предложен алгоритм вычисления функции релевантности на основании метода N-gram.

Реализация алгоритма шифрования RSA на языке.

RSA алгоритм, относящийся к шифрованию на открытом ключе, соответственно

Вычисляется значение функции Эйлера от числа n

Описание алгоритма. На языке программирования LabVIEW алгоритм RSA должен быть реализован как минимум из трех блоков

Обзор некоторых алгоритмов нестрогого сопоставления записей.

Рассмотрим следующие алгоритмы нестрогого поиска

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

Порядок букв в слове абсолютно никакого значения не имеет.

Разработка алгоритма нечеткого поиска на основе хэширования

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

Программная реализация алгоритма Левенштейна для.

В статье описан пример реализации алгоритма Левенштейна на языке PL/SQL для

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

Применение методов text mining для классификации информации.

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

Алгоритм TF выбрал тексты на основании частотного словаря и включил в коллекцию документы далекие по смыслу от исходного.

Реализация алгоритма Metaphone для кириллических фамилий.

Ключевые слова база данных; фонетический алгоритм; Metaphone; Soundex; генерация ключа; ключ Metaphone; сравнение строк; поиск данных

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

Пост-квантовый алгоритм электронно-цифровой подписи на.

Решать его требуется без структур и (очень желательно) без классов.
До сих пор не могу ничего придумать по поводу поиска одинаковых слов и самое проблематичное : упорядочивание по алфавиту. все буквы латинские.

А STL контейнеры использовать можно?
И в чем проблема сравнивать латинскии буквы? strcmp есть например.

Пускай есть значения полученные с помощью strtok о положении всех раздельных слов в символьном массиве string, как мне пользоваться "strcmp" для сравнивания слова с последующими, и как заставить алгоритм посчитать их суммарное количество, после чего не заставлять считать количество того же слова, которое было уже посчитано. Чтоб мы не получили например результат: из строки "qwerty qaz qwerty qwerty".

qwerty 3
qaz 1
qwerty 2
qwerty 1

Я думаю задание с алфивитом можно не рассматривать как обязательное, а вот подсчёт слов было бы очень желательно сделать.

а где вы собираетесь хранить ваши значения? можно конечно извратиться, взять массив слов, массив счетчик . - 100% изврат, имхо, который и делать не стоит. Я бы взяла хотябы связанный список, при получении очередного слова обойти весь список и сравнить с каждым существующем словом, если нет - добавляем узел(упорядоченно добавлять), если есть - увеличиваем счетчик на один. Список конечно же состоит из структур: указатель/и на следующий/предыдущий элемент списка, указатель на строку(слово), ну и счетчик.

Связанные списки - подход программиста, может быть это и лучше, но например для меня это просто очень сложно для понимания, просто нету опыта. К тому же преподаватель сказал что лучше решать без них.

Хотя, я бы не отказался от решения даже со связанными списками, лишь бы оно работало и всё было понятно откуда берётся.

Я прекрасно понимаю, что по началу со списками тяжело, но возможно сесть, поучить матерьял, а на форуме задавать конкретные вопросы. Лично я ваши лабы писать не буду.

Вот интересно. STL использовать нельзя - дескать "подход профессионального программиста", а самому писать списки (без них - сплошной геморрой), сортировку, "парсер" и прочее - можно. Это, все таки, позиция преподавателя, или ваши личные предпочтения?

P.S. Так все-таки, какой язык предлагается для решения задачи? Уже миллион раз указывалось, что С и С++ - суть разные вещи.

Ага. А ведь strtok, strcmp - это для С-style string. И как быть?

А чем не нравится вариант с массивом? Имхо, самое простое и очевидное решение - создать массив слов и отсортировать его по алфавиту. А затем пройтись по отсортированному массиву, подсчитать частоту каждого слова и выдать результаты на экран. Все! И никаких там связных списков, структур и классов, столь ненавистных автору :)

2Lerkin
А разве в С++ запрещено использовать С-style стрки?

Возможно :) А как предлагаешь организывать массив, если заранее кол-во слов неизвестно.

Ну, можно сначала посчитать слова, а потом создать массив. А можно просто ограничить количество слов каким-нибудь числом. Например, длиной строки. Ведь количество слов никак не может быть больше, чем количество символов в строке.
А если еще учесть, что слова должны быть разделены как минимум одним пробелом, то получится, что количество слов в строке s не может превышать 1+strlen(s)/2.

Имеется ввиду STL(список).
[LEFT]Такие задачи,как раз,надо делать с STL.Классический пример по созданию словаря из книги Стенли Липпмана.Язык программирования С++.Используется vector и map.C.Липпман решает похожую задачу: считывает текстовый файл,в котором находится книга Кэррола "Алиса в стране Чудес" и составляет словарь автора,т.е. определяет сколько он использует слов,сколько встречаются в тексте те или инные слова. Задача,кстати,не такая уж и простая.Правда,Липпман делает это очень изящно,он убирает пробелы, знаки препинания,союзы,приводит слова к стандарной форме (без падежей).К чему я это говорю - он использует, почему,то STL ? Почему ? Вот и подумай кому будет лучше решать без них ? Точно не тебе,как программисту.Какой язык вы учите ? С++ ? Зачем тогда С-style ? У тебя задача похожа на ту,что решает Липпман, только он пользуется как программист преимуществами С++,а ты ограничен достаточно жесткими рамками.Т.е мало того,что квалификация Липпмана несоизмерима с твоей(он один мировых авторитетов в С++,а ты студент),так тебе еще навязываны эти рамки. На С++ с STL решение твоей задачи будет строк 10( . ),если хочешь могу набросать,минут за 15 а на С. имхо:не самая простая задача(это ж словарь,значит дубли надо поудалять,отсортировать,т.е ф-ию написать и т.д.) - 1.5 часа думаю.
P.S.Такие ограничения - зло,поскольку не дают возможность студентам использовать С++.Студенты думают,что учат С++,а на самом деле учат С с классами,как говорит Б.Страуструп.Считаю,что любая задача должна решаться наиболее простыми и современными способами,а не сложными и устаревшиими.[/LEFT]

Я бы не отказался и от примера выполнения Липпмана, и от STL. (если я правильно написал)
Задача нужна почти в любом варианте и срочно!
Я не хочу губить одной нерешённой задачей всю курсовую и экзамен.
Защитить то я её скорее всего смогу, но написать никак не выходит.

Подсчитывает кол-во слов и сортирует(map),все дубли удалены.Преподавателю скажи,что пользовался Липпман.Язык программирвания С++.Вводный курс.;)

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
wcout.imbue(locale(".866"));
wcout vec;
while(cin >> s)
vec.push_back(s);
wcout v;
for(size_t i = 0;i ::iterator it = find(vec.begin(),vec.end(),vec);
for(vector ::iterator iter = vec.begin();
iter != vec.end();++iter) if(*iter == *it) ++count;
>
v.push_back(count);
>
map m_map;
for(size_t i = 0;i ::iterator iter = m_map.begin();iter !=
m_map.end();++iter) cout first second

2 m_Valery - Не могу добавить отзыв, и потому высказываю здесь свою уважение за пропаганду STL:).

Имеется ввиду STL(список).
[LEFT]Такие задачи,как раз,надо делать с STL.Классический пример по созданию словаря из книги Стенли
Липпмана.Язык программирования С++.Используется vector и map.C.Липпман
решает похожую задачу:считывает текстовый файл,в котором находится книга Кэррола "Алиса в
стране Чудес" и составляет словарь автора,т.е. определяет сколько он использует слов,сколько
встречаются в тексте те или инные слова.Задача,кстати,не такая уж и простая.Правда,Липпман
делает это очень изящно,он убирает пробелы,знаки препинания,союзы,приводит слова к стандарной
форме(без падежей).К чему я это говорю - он использует,почему,то STL ? Почему ? Вот и подумай
кому будет лучше решать без них ? Точно не тебе,как программисту.Какой язык вы учите ?
С++ ? Зачем тогда С-style ? У тебя задача похожа на ту,что решает Липпман,только он пользуется как программист
преимуществами С++,а ты ограничен достаточно жесткими рамками.Т.е мало того,что квалификация
Липпмана несоизмерима с твоей(он один мировых авторитетов в С++,а ты студент),так тебе еще навязываны
эти рамки.На С++ с STL решение твоей задачи будет строк 10( . ),если хочешь могу набросать,
минут за 15 а на С. имхо:не самая простая задача(это ж словарь,значит дубли надо поудалять,
отсортировать,т.е ф-ию написать и т.д.) - 1.5 часа думаю.
P.S.Такие ограничения - зло,поскольку не дают возможность студентам использовать С++.Студенты
думают,что учат С++,а на самом деле учат С с классами,как говорит Б.Страуструп.Считаю,что любая
задача должна решаться наиболее простыми и современными способами,а не сложными и устаревшиими.[/LEFT]

Вот этот пост, если из него убрать лишние эмоции;), можно вывесить в прилепленные темы данного раздела, имхо. Чтобы студент, изучающий С++, сам понял, что это такое на самом деле. И не стеснялся распечатать эти слова и показать их косному преподавателю.
Скромное замечание по существу поста.
Единственно, могу сказать что эта книга по уровню и глубине охвата STL - далеко не самая мощная (субъективно, но многие думаю, согласятся). Но, по понятности и доступности объяснений она очень хороша, и m_Valery совершенно правильно советует ее. Я присоединяюсь.

.
Скромное замечание по существу поста.
Единственно, могу сказать что эта книга по уровню и глубине охвата STL - далеко не самая мощная (субъективно, но многие думаю, согласятся). Но, по понятности и доступности объяснений она очень хороша, и m_Valery совершенно правильно советует ее. Я присоединяюсь.

Да,разумеется, это не Николай Джосьютис "Стандартная библиотека для профессионалов";)
Книга Липпмана и не претендует на статус книги по STL.
Содержание книги Липпмана соответсвует своему собственному названию "Язык программирования С++.Вводный курс". У нее есть преимущества,наверно,есть и недостатки.Мне нравится,что Липпман обходится без С-style,никаких массивов,С-строк,макросов и т.д.Ту же задачу по составлению словаря он решает с map. Хотя бы потому,что тот же Алекс Степанов(помним,что он - создатель STL) в своей книге "Стандартная библиотека шаблонов С++"
упорно называет мар не отображением,а cловарем. Если это словарь,то о каких массивах стоит, вообще, говорить в этой задаче ? :D Книга Липпмана описывает С++,в соответствии со
стандартом.(соавтором при написании была Жози Лажойе,одна из разработчиц стандарта)
Из студенческих учебников,думаю,книга Липпмана одна из лучших.Попались,как то ,мне в руки методические указания для студентов-программистов.Предмет называется просто,но со вкусом-"С++".30 уроков,после 15 - зачет по С(,причем тут С! до С++ еще не добрались),далее 2 урока - структуры(это то же С),7 уроков-классы, остальные работа с файлами в С и работа с файлами в С++.Все.Из 30 уроков по С++ - 10(мало).Зато далее по MFC - 60 уроков(не много ли?)
Почитал,мое мнение-отрава.Безцеремонно содрано с Дейтела, фактически из С++ только классы(изложены очень поверхностно).Про STL - ни слова.Понять по этой методичке,например,полиморфизм, наследование практически нереально.
Читая эту методичку,мне вспомнились слова Страуструпа:"Знание С не является обязательным для изучения С++. Чем лучше вы знаете С,тем труднее вам будет избежать программирования на С++ в стиле С,теряя при этом потенциальные преимущества С++."И далее там же:"
из Рекомендаций для программистов на С
. [3] Не используйте malloc(),оператор new делает то же самое,только лучше.Вместо realloc() пользуйтесь vector.
. [5]Сведите к минимуму использования массивов символов и строк С.Стандартные библиотеки классов С++ string u vector упрощают программирование по сравнению с традиционным стилем С."
Не следует так же забывать то,что STL разрабатывался лучшими экспертами С++и игнорировать их труд,что бы облегчить свой собственный по-моему не разумно.
P.S.Может,действително,стоит завести отдельную тему.Вопрос о соотношении С и С++,о негласном запрете STL и других ограничениях постоянно возникает при решении студенческих задач.
Что это за явление,почему возникло и чем обернется ? Там и обсудим.ИМХО:это интересно.

В курсовой подобное задание.
Но, к сожалению, требовалось создать класс "Частотный словарь" используя массивы. Другие задания были создать классы список, стек и т.д. и реализовать действия с ними.

Как объяснить преподователю, бессмысленность изобретания велосипеда? ,)

Я бы на такого преподавателя "наехал" и доходчиво объяснил ему, что С++ без структур и классов - это ассемблер, и подобную задачу надо ставить в соответствующей дисциплине. Хотя, даже на ассемблерах пользуются структурами.

2 m_Valery
У меня похожая задача. необходимо создать частотный словарь категоризировать слова в текстАХ, то есть существует несколько типов текстов. поэтому нужно вести неск частот (допустим три типа текстов) для каждого слова - частота вхождения в первый тип текста, частота вхождения слова во второй и частота вхождения в третий тип текста.
Как с пом STL более рационально вести словарь?
2 ALL
К сожалению, плохо знаком с STL и был бы признателен, если б вы объяснили как с пом данной библиотеки обновлять статистику частот, то есть сравнивать каждое слово с уже имеющимся в словаре и увеличивать частоту при совпадении.

Можно сделать. хотя и труднее.Могу предложить такой вариант. Допустим есть 3 файла,в каждом из которых некий текст.Считываем каждый файл в отдельный вектор строк.Считываем так:

. ifstream in1("f1.txt");
istream_iterator ifile1(in1);
istream_iterator eos1;
vector coll1;
copy(ifile1,eos1,inserter(coll1,coll1.begin()));.

После этого каждый вектор содержит слова из соответсвующего файла.Далее используем множество set и сливаем содержимое каждого вектора в него.В set получим только уникальные слова,без повторов.Теперь надо подсчитать сколько раз каждое слово содержиться в том или ином файле и занести куда то результаты. Я использовал вектор векторов,для этого обьявил typedef vector > T; и создал такой 2мерный вектор так

где collection.size() - кол-во строк этого вектора,т.е длина set или количество уникальных слов,количество столбцов 3,т.е это количество файлов.Все элементы этого вектора равны нулю изначально.Нужно определить сколько раз встречается каждое слово из множества в каждом из файлов.Сделать это можно так для одного файла,пришлось повторить этот кусок кода трижды для каждого из файлови заполнить 2мерный вектор по столбцам.

.
size_t k = 0;
for(set ::iterator it = collection.begin();it != collection.end();++it) int count1 = 0;
set ::iterator it1 = find(collection.begin(),collection.end(),*it);
for(vector ::iterator iter = coll1.begin();
iter != coll1.end();++iter)
if(*iter == *it1) <
++count1;
mass[k][0] = count1;
>
++k;
>
k = 0;.

После этого мы имеем 2мерный вектор,количество строк которого равно - количеству уникальных слов,а кол-во столбцов -это количество файлов.Вектор векторов содержит нужные нам частоты.Практически все готово.Осталось только заполнить сам словарь, т.е контейнер STL map.Однако,есть один ньюанс.Этот словарь должен в качестве ключа содержать слово,а в качестве значения - вектор.Как это сделать ? Очень просто.Для этого обьявляем typedef vector frequency; - это частота. И все.Вот теперь создадим словарь.map freqDictionary;Осталось только его заполнить

.
size_t i = 0;
for(set ::iterator it = collection.begin();
it != collection.end();++it) freqDictionary.insert(map ::value_type(string(*it),
frequency(mass)));
++i;
>.

и потом распечатать результат.Это первое,что пришло в голову. В принципе готовый код могу дать,но попытайся сделать сам,очень полезно.

диплом весь готов. кроме этого модуля:(
m_Valery, как более рационально и быстрее сделать? с помощью ф-ций STL или с пом стандартных ф-ций С\С++? каких? (с С++ познакомился только неск месяцев назад:() буду очень благодарен за консультацию эксперта.
PS: прошу прощения за отдельно созданную тему. не разобрался с форумом.

.
диплом весь готов. кроме этого модуля:(
m_Valery, как более рационально и быстрее сделать? с помощью ф-ций STL или с пом стандартных ф-ций С\С++? каких? (с С++ познакомился только неск месяцев назад:() буду очень благодарен за консультацию эксперта.
.

Прочитал эту очень интересную ветку.
У меня схожая проблема, только вот текст:

"Import SAM and SYSTEM Registry Files" –
the importing of user data from SAM registry file. If the imported SAM file is additionally encrypted by SYSKEY (enabled by default in Windows 2000/XP/2003/Vista), the program will also need the SYSTEM Windows registry file, located at the same Windows directory, where SAM file was – %SystemRoot%\System32\Config. Copies of these files may be also found in the %SystemRoot%\Repair and %SystemRoot%\Repair\RegBack folders. (Note: %SystemRoot% is the system folder of Windows OS; commonly C:\WINDOWS or C:\WINNT).

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

Вот наконецто нашел время отписаться)) написал прогу, защитил диплом)
БОЛЬШОЕ СПАСИБО за книгу. очень помогла.
ск понадобилось времени на изучение STL? полдня:cool: естественно на изучение ТОЛЬКО необходимого материала)))

2 m_Valery.
ск понадобилось времени на изучение STL? полдня:cool: естественно на изучение ТОЛЬКО необходимого материала)))

Оффтоп:
Не торопись:) И не говори никому. ;) Я когда это прочел вспомнил слова Скотта Маейрса,он любит иногда посетовать на то,что он не достаточно хорошо знает С++,что не до конца понимает STL,то,говорит, в шаблонах слабоват. D

m_Valery можете скинуть исходник там где из трех файлов в одно множество скидываете. пожалуйста. седня экзамен. у меня похожее задание было как экзаменационная работа! ничего не успеваю(((

Зачем это нужно

Что нового?

GIF

Начиная с версии 1.1.5 появились две новые кнопки. Кнопка Экспорт позволяет выгрузить данные словаря на отдельный лист. Говорят, что это нужно людям занимающимся контекстом. Как это работает видно на картинке слева. Кроме этого, теперь можно выбрать галочкой любой термин (или несколько) в словаре и закрасить ячейку содержащую термин цветом. После этого закрашенные ячейки можно, например, выбрать через стандартный фильтр по цвету и удалить. Кроме этого исправлена утечка памяти и словарь теперь не боится большого количества строк. Если в файле 100 000 строк словарь строится довольно быстро.

Читайте также: