Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32

Хеш-таблица

09.01.2019, 22:12. Показов 1606. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем, привет! Реализовал словарь на основе хеш-таблицы. Ключ - это буква, на которую начинаются слова, например, "а" - все слова на "а" и т.д. Задача такая: задаётся исходное слово, необходимо из его букв составить слова. Мой алгоритм работает так: переопределил ассоциативный контейнер так, чтобы ключами являлись буквы алфавита, т.е. значениями будут слова, которые начинаются на а, на б и т.д. После я заполняю ассоциативный контейнер words, который содержит слова, начинающиеся на определенную букву и ключами являются их длины. После мы ищем слова в words, длина которых не больше длины заданного слова( это хорошо работает на словах средней и маленькой длины). При длинных словах, чтобы избежать перебора всего словаря, создан контейнер letters_of_word который содержит не повторяющиеся буквы заданного слова. В начале заполнения структуры words проверяется условие на присутствие буквы в контейнере letters_of_word.(Это условие позволяет отсеять повторяющиеся буквы). Таким образом, мы проходим не весь словарь, а только слова, которые начинаются на буквы заданного слова. Можно ли улучшить данный алгоритм?) Исходный код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<iostream>
#include<fstream>
#include<string>
#include<set>
#include<clocale>
#include<codecvt>
#include<iterator>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<map>
 
class Trie
{
private:
    size_t count = 0;
public:
    std::set<std::wstring> Res; // полученные слова
    std::unordered_multimap<std::wstring, std::wstring> dictonary; //словарь
    std::multimap<size_t, std::wstring> words; // хранение слов опеределенной длины и начинающихся на конкретную букву
    std::map<std::wstring, int> letters_of_word; // буквы заданного слова, контейнер не содержит повторяющиеся буквы
    std::vector<wchar_t> word;// для хранения заданного слова
    bool LoadDictonary(char* Filename);
    void GuessWord(std::wstring str, size_t length);
};
 
 
bool Trie::LoadDictonary(char* Filename) //загрузка словаря
{
    std::wifstream wif(Filename);
    std::locale utf8_locale(std::locale(), new std::codecvt_utf8<wchar_t>);
    wif.imbue(utf8_locale);
    wchar_t bom = L'\0';
    wif.get(bom);
    std::wstring Buff = L"";
    while (!wif.eof())
    {
        wif >> Buff;
        if (Buff.find_first_of(L"ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ") != std::wstring::npos) // если есть заглавные буквы
        {
            continue;
        }
        if (Buff.find_first_of(L"~`!@#$%^&*()_+=-?><.,\\|/;:'""№qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890") != std::wstring::npos)
        {
            continue;
        }
        dictonary.emplace(Buff.substr(0,1), Buff);
    }
    wif.close();
    Buff.clear();
    return true;
}
 
void Trie::GuessWord(std::wstring str, size_t length) // поиск слов, основной алгоритм 
{
    std::wstring temp = str;
 
    for (size_t i = 0; i < temp.size(); ++i)
    {
        word.push_back(temp[i]);
    }
 
    for (size_t i = 0; i < length; ++i)
    {
        if (letters_of_word.find(str.substr(i,1))->first == str.substr(i,1))
        {
        
            
            auto range = dictonary.equal_range(temp.substr(i, 1));
            for (std::unordered_multimap<std::wstring, std::wstring>::iterator it = range.first; it != range.second; ++it)
            {
                words.emplace(it->second.size(), it->second);
            }
            for (std::multimap<size_t, std::wstring>::iterator it = words.begin(); it != words.end(); ++it)
            {
                if (it->first <= length)
                {
            
                    for (size_t j = 0; j < it->second.size(); ++j)
                    {
                        auto pos = std::find(word.begin(), word.end(), it->second[j]);
                        if (pos != word.end())
                        {
                            count++;
                            word.erase(pos);
                        }
                    }
                    if (count == it->second.size())
                    {
                        Res.insert(it->second);
                    }
                    count = 0;
                    word.clear();
                    for (size_t k = 0; k < temp.size(); ++k)
                    {
                        word.push_back(temp[k]);
                    }
                }
                else break;
            }
        
            letters_of_word.erase(str.substr(i,1));
        }
    }
    letters_of_word.clear();
}
 
int main(int argc, char *argv[])
{
 
    Trie tr;
    std::wstring Word = L"";
 
    if (argc < 4)
    {
    std::wcout << L"error" << std::endl;
    return -1;
    }
 
    std::wofstream out(argv[3]);
    std::locale utf8_locale1(std::locale(), new std::codecvt_utf8<wchar_t>);
    out.imbue(utf8_locale1);
    if (!out)
    {
        return -1;
    }
 
 
    std::wifstream input(argv[2]);
    std::locale utf8_locale(std::locale(), new std::codecvt_utf8<wchar_t>);
    input.imbue(utf8_locale);
    wchar_t bom = L'\0';
    input.get(bom);
    if (!input)
    {
        out << L"error" << std::endl;
        return -1;
    }
 
    if (tr.LoadDictonary(argv[1]) == false) // словарь
    {
        out << "error" << std::endl;
        return -1;
    }
 
 
 
    input >> Word;
    
    if (Word.find_first_of(L"ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮ") != std::wstring::npos) // если есть заглавные буквы
    {
        out << L"error" << std::endl;
        return -1;
    }
    if (Word.find_first_of(L"~`!@#$%^&*()_+=-?><.,\\|/;:'""№qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890") != std::wstring::npos)
    {
        out << L"error" << std::endl;
        return -1;
    }
    size_t L = Word.size();
    for (int i = 0; i <L; ++i)
    {
        tr.letters_of_word.insert(std::pair<std::wstring, int>(Word.substr(i, 1), (int)Word[i]));
    }
    tr.GuessWord(Word, L);
    for (auto i : tr.Res)
    {
        out << i << std::endl;
    }
    tr.Res.clear();
    tr.dictonary.clear();
    input.close();
    out.close();
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
09.01.2019, 22:12
Ответы с готовыми решениями:

Хеш таблица
Скажите, в чём польза от хеш-таблицы? Только в скорости поиска?

Хеш-таблица
В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер...

Хеш-таблица
В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер...

7
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
09.01.2019, 22:33
Цитата Сообщение от VAS77 Посмотреть сообщение
задаётся исходное слово, необходимо из его букв составить слова
Главный вопрос, что в контексте задачи понимается под словом?

Добавлено через 3 минуты
Цитата Сообщение от VAS77 Посмотреть сообщение
Задача такая: задаётся исходное слово, необходимо из его букв составить слова
Какое отношение имеет словарь, загружаемый из файла, к решаемой задаче?
0
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
09.01.2019, 22:42  [ТС]
nonedark2008, слово - это строка(набор букв, например - "шишка"), записанная в контейнер word, берется из файла. Нужно найти такие слова из словаря, которые можно составить из заданного слова, т.е использовать те символы, которые есть в заданной строке.
Например в argv[2] задано слово шишка
В argv[3] запишутся слова
а
и
ишак
к
ш
шик
шиш
шишак
шишка
Вложения
Тип файла: zip dictonary.zip (350.2 Кб, 4 просмотров)
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.01.2019, 00:00
Цитата Сообщение от VAS77 Посмотреть сообщение
Можно ли улучшить данный алгоритм?
Зависит от того, что ты хочешь улучшать. Можно оптимизировать общее время поиска для одного слова (от момента загрузки словаря, до получения всех слов, подпадающих под ограничения задачи). А вот если предполагается, что словарь у нас один, а вот запросов на поиск будет много, - это уже совершенно другая задача.

В первом случае не вижу способа лучше, чем последовательно читать каждое слово и сразу же его проверять на соблюдение условий. Ты в своем решении зачем-то разделил слова по первой букве:
Цитата Сообщение от VAS77 Посмотреть сообщение
Таким образом, мы проходим не весь словарь, а только слова, которые начинаются на буквы заданного слова
что потребовало от тебя проверить каждую первую букву всех слов. Но при решении "влоб" эти слова и так были бы отброшены при проверке первой буквы.

Второй случай сильно зависит от размера словаря, от ограничений по памяти и от необходимой скорости работы.
0
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
10.01.2019, 17:10  [ТС]
nonedark2008,
Цитата Сообщение от nonedark2008 Посмотреть сообщение
В первом случае не вижу способа лучше, чем последовательно читать каждое слово и сразу же его проверять на соблюдение условий.
Если мы будем проходить так слова и проверять их на условия, то при большой длине слова ( >= 20 символов) пройдём весь словарь, что не очень эффективно. (мой словарь содержит слова, максимальная длина которых 18 символов).
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Ты в своем решении зачем-то разделил слова по первой букве:
Я разделил слова по первой букве, для того чтобы не проходить весь словарь,т.е. будем проходить только те слова, которые начинаются на букву, которая есть в заданном слове.
В принципе сложность моего алгоритма зависит от размера словаря, т.е линейна. Может быть можно как то улучшить ещё?)
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.01.2019, 18:19
Цитата Сообщение от VAS77 Посмотреть сообщение
Я разделил слова по первой букве, для того чтобы не проходить весь словарь
Ты и так проходишь весь словарь, когда читаешь его из файла.
Такого рода оптимизации имели бы смысл, если запросов было бы много, а так...
0
0 / 0 / 0
Регистрация: 29.09.2018
Сообщений: 32
10.01.2019, 18:29  [ТС]
nonedark2008, а если не оптимизировать чтение из словаря, а оптимизировать поиск подходящих слов?
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.01.2019, 19:28
Цитата Сообщение от VAS77 Посмотреть сообщение
а если не оптимизировать чтение из словаря, а оптимизировать поиск подходящих слов?
Если предположить, что время загрузки и обработки словаря не важно, то можно сделать следующее.
Взять каждое слово из словаря, отсортировать все буквы в алфавитном порядке. А затем из преобразованных слов построить префиксное дерево. По такому дереву можно передвигаться, сразу игнорируя те ветви, которые однозначно не могут быть порождены из заданного слова.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.01.2019, 19:28
Помогаю со студенческими работами здесь

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

Хеш Таблица
я хочу, чтобы у меня был массив структур, каждая из которых содержала некоторое значение и ссылку на следующий элемент этого массива ...

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

хеш таблица
в чем ошибка #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;iterator&gt; #include &lt;algorithm&gt; #include &lt;string&gt; struct...

Хеш-таблица
Что является элементами хеш-таблицы?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
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. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru