Словарь частоупотребимых слов

@prizrak39 · Регистрация: 10.12.2012

Студворк — интернет-сервис помощи студентам

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

Code
1
2
3
qard 10
qanojd 20
qaretachd 1

Далее задаются символы.

Code
1
2
q
qar

В результате должно вывестись следующее.

Code
1
2
3
4
5
qanojd
qard
qaretachd
qard
qaretachd

Надеюсь суть задания понятно изложил.
Я думаю решать следующим образом. Хранить данные в двумерном массиве, распологая их в порядке убывания частоты упоминания. А затем поиск значений осуществлять по всему массиву сверху на совпадения, если совпадение найдено, тогда они будут находится в порядке убывания.
Но есть один момент. Если частота упоминаний совпадает, тогда вывод необходимо осуществлять в алфавитном порядке.
Возможно кто поскажет правильный ли вариант решения я выбрал, а также сортировку лучше производить в процессе считывания, или после окончания считывания всех введенных слов?

@Igor3D · 25.02.2013, 22:07

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

Если так то все очень банально: сортируете словарь (одномерный массив).по алфавиту, при вводе ищете минимальное совпадающее. Потом идете вправо по словарю пока совпадения не кончились. В результате известен диапазон подходящих индексов, напр [10-15]. Делаете временный массив индексов и сортируете его по частоте, вот и все

@prizrak39 · 25.02.2013, 23:05 **[ТС]**

Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял.

@gazlan · 25.02.2013, 23:34

Небходимо использовать не массив слов, а массив записей (пар) типа слово-счетчик. При сортировке слова и их счетчики будут сцеплены.

@prizrak39 · 25.02.2013, 23:36 **[ТС]**

Лучше наверное использовать списки?

@iama · 25.02.2013, 23:48

prizrak39, сортируете просто массив структур, а потом проходите за линию за запрос. Вообще, можно тут бор припилить, но это слишком сложно, мне кажется, для ваших потребностей.

@prizrak39 · 25.02.2013, 23:52 **[ТС]**

Из всего я понял что лучше всего отсортировать массив по алфавиту и в нем уже осуществлять поиск. Интересно а возможно сортировать массив по мере чтения значений?

@iama · 25.02.2013, 23:57

Сообщение от prizrak39

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

Сообщение от prizrak39

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

Противоречие.

@prizrak39 · 26.02.2013, 00:03 **[ТС]**

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

@gazlan · 26.02.2013, 00:18

Примерно так (сортировка по двум ключам):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
if (p1->v1 > p2->v1)
{
   return 1;
}
else if (p1->v1 < p2->v1)
{
   return -1;
}
else
{
   if (p1->v2 > p2->v2)
   {
      return 1;
   }
   else if (p1->v2 < p2->v2)
   {
      return -1;
   }
   else
   {
      return 0;
   }
}

@prizrak39 · 26.02.2013, 00:21 **[ТС]**

Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял?

@gazlan · 26.02.2013, 00:25

Да, правильно. По частоте - в обратном порядке ключей, по алфавиту - в прямом. Если будете использовать массив структур, рекомендую стандартный qsort().

@prizrak39 · 26.02.2013, 00:26 **[ТС]**

Большое спасибо постараюсь реализовать.

@Igor3D · 26.02.2013, 11:31

Сообщение от prizrak39

Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял.

Ну вот в результате поиска выяснилось: подходят слова с 10 по 15 в словаре. Делаете массив int { 10, 11, 12, 13, 14, 15 } и сортируете его напр таким функтором

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Word {
 string mText;      // слово
 int mFrequency;  // частота
};
 
struct CompFrequency {
 CompFrequency( const vector  <Word> & data ) : mData(data) {}
 bool operator () ( int i1, int i2 ) const
 {
   return mData[i1].mFrequency > mData[i2].mFrequency;
 }
 
 const vector  <Word> & mData; 
}; 
 
// использование
vector  <Word>  dictionary; 
vector <int> temp;  // заполнили temp
...
std::sort(temp.begin(), temp.end(), CompFrequency(dictionary));

Добавлено через 3 минуты

Сообщение от prizrak39

Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял?

По-моему совершенно неправильно

. Отсортировав по первому ключу = частота Вы не сможете найти нужные слова

@prizrak39 · 26.02.2013, 11:40 **[ТС]**

Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно?

@Igor3D · 26.02.2013, 12:02

Сообщение от prizrak39

Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно?

Не по всему, если массив отсортирован по алфавиту то просто lower_bound (найти первый подходящий) и upper_bound (найти первый НЕподходящий). Это быстрые поиски

@prizrak39 · 26.02.2013, 18:42 **[ТС]**

А не подскажите какой лучше тип данных использовать? Например в C#. List я думаю не подходит, ArrayList возможно, тогда необходимо будет в нем хранить структуру?

@gazlan · 26.02.2013, 19:21

Сообщение от Igor3D

По-моему совершенно неправильно

. Отсортировав по первому ключу = частота Вы не сможете найти нужные слова

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

Делать надо именно так, как сказано в #10.

Если вам непонятно, что такое multikey sort, посмотрите в литературе.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@Igor3D 1969 / 825 / 115 Регистрация: 01.10.2012 Сообщений: 4,890 Записей в блоге: 2
	25.02.2013, 22:07
	Может лучше сформулировать так: человек набирает какой-то текст, а ему выпадает напр popup menu в котором список всех слов из словаря начинающихся с введенной части. Если так то все очень банально: сортируете словарь (одномерный массив).по алфавиту, при вводе ищете минимальное совпадающее. Потом идете вправо по словарю пока совпадения не кончились. В результате известен диапазон подходящих индексов, напр [10-15]. Делаете временный массив индексов и сортируете его по частоте, вот и все 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:05 [ТС]
	Массив по алфавиту я отсортирую, а как мне их потом связать с их частотой? Этот момент я не совсем понял. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	25.02.2013, 23:34
	Небходимо использовать не массив слов, а массив записей (пар) типа слово-счетчик. При сортировке слова и их счетчики будут сцеплены. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:36 [ТС]
	Лучше наверное использовать списки? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	25.02.2013, 23:48
	prizrak39, сортируете просто массив структур, а потом проходите за линию за запрос. Вообще, можно тут бор припилить, но это слишком сложно, мне кажется, для ваших потребностей. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	25.02.2013, 23:52 [ТС]
	Из всего я понял что лучше всего отсортировать массив по алфавиту и в нем уже осуществлять поиск. Интересно а возможно сортировать массив по мере чтения значений? 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:03 [ТС]
	Если сортировать в порядке возрастания, то не совсем понятно как внутри одинакового количества упоминаний выводить значения по алфавиту. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:21 [ТС]
	Сначала сортируем по частоте, а потом внутри каждых одинаковых значений по алфавиту. Я правильно понял? 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.02.2013, 00:25
	Да, правильно. По частоте - в обратном порядке ключей, по алфавиту - в прямом. Если будете использовать массив структур, рекомендую стандартный qsort(). 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 00:26 [ТС]
	Большое спасибо постараюсь реализовать. 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 11:40 [ТС]
	Тогда получается необходимо пробежать по всему введенному массиву и найти совпадения и записать их в отдельный массив. Далее отсортировать этот массив по частоте. Правильно? 0

@prizrak39 0 / 0 / 0 Регистрация: 10.12.2012 Сообщений: 34
	26.02.2013, 18:42 [ТС]
	А не подскажите какой лучше тип данных использовать? Например в C#. List я думаю не подходит, ArrayList возможно, тогда необходимо будет в нем хранить структуру? 0