Trie структура данных в словаре, чтобы найти рифмованные слова

-2

Я работаю над своей функцией, которая найдет рифмованные слова из текстового файла словаря, содержащего 40 000 слов. Например, я вхожу в akes, и это дает напечатанное слово «rakes sakes takes». Поэтому я знаю, что для этого требуется структура данных с несколькими переменными. Может быть bool было бы лучшим заявлением для isWord вместо int? Таким образом, функция, которую я показываю, - это измененная функция, потому что исходная функция может печатать только одно слово, которое рифмуется с вводом пользователя. Поэтому мне нужно будет построить структуру данных в версии Trie. Честно говоря, я довольно ужасен в структуре данных, поэтому, пожалуйста, несите меня.Trie структура данных в словаре, чтобы найти рифмованные слова

struct Node 
{ 
    char c; 
    Node* letters[26]; 
    bool isWord; 
}; 

bool findWords(Node*& pTail, char dictionary[][MaxLength + 1], int numberOfDictionaryWords) 
{ 
    Node* pHead; 
    pHead = pTail->letters[26]; 
    bool found = false; 
    int first = 0; 
    int last = numberOfDictionaryWords - 1; 
    int middle = (first + last)/2; 

    while (first <= last) 
    { 
     if (strncmp(pHead, dictionary[middle], strlen(pTail)) > 0) 
     { 
      first = middle + 1; 
     } 
     else if (strncmp(pHead, dictionary[middle], strlen(pTail)) == 0) 
     { 
      char theWord[MaxLength + 1]; 
      memcpy(theWord, dictionary[middle], sizeof(char) * (MaxLength + 1)); 
      cout << "Words(s) found: " << strReverse(theWord) << endl; 
      found = true; 
      break; 
     } 
     else 
     { 
      last = middle - 1; 
     } 
     middle = (first + last)/2; 
    } 
    return found; 
}

INT в main():

Node* pTail = NULL; 
char dictionary[Rows][MaxLength + 1]; 
int numberOfWords = 0; 
readFile(dictionary, numberOfWords); 
sortDictionaryInReverse(dictionary, numberOfWords); 
char aWord[MaxLength]; 
cout << "Enter the suffix to find rhyming words: "; 
cin >> aWord; 
convertToLowerCase(aWord, strlen(aWord)); 
strReverse(aWord); 

if (findWords(aWord, dictionary, numberOfWords)) 
{ 
    cout << "This rhyming word is in the dictionary. \n"; 
} 
else 
{ 
    cout << "This rhyming word is not in the dictionary. \n"; 
}

источник

2014-11-26 Cam9191

Процессор обычно обрабатывает 'int' так же быстро, как' bool'. Вы использовали бы только «bool» для упаковки, что замедляет выполнение. Профилировали ли вы свой код, чтобы узнать, где узкое место? –

Я предлагаю вам использовать другую структуру данных, что более подходит для ваших целей. Например, у вас может быть массив из 26 списков или деревьев, по одному для каждой буквы. Это уменьшит ваш первый доступ к O (1), поскольку вы можете использовать букву для индексации в массив; нет поиска. –

Я думаю, что std::multimap будет лучшим выбором.

Ваши не-слова будут ключами, а рифмованные слова будут значениями.

Таким образом, вы можете установить его так:

std::multimap<std::string, std::string> foo; 

foo.insert(std::make_pair("akes", "rakes")); 
foo.insert(std::make_pair("akes", "sakes")); 
foo.insert(std::make_pair("akes", "takes"));

Если вы хотите сказать, печатающие все рифмы «AKES» вы можете сделать:

std::cout << "akes\n\t"; 
for(auto i = foo.equal_range("akes"); i.first != i.second; ++i.first){ 
    std::cout << i.first->second << ' '; 
}

Если вы хотите напечатать из первого элемента вы могли бы сделать это:

std::cout << "akes " << foo.find("akes")->second;

источник

2014-11-26 02:18:27

Trie структура данных в словаре, чтобы найти рифмованные слова

ответ

Смежные вопросы