Поиск предложений по реализации Word Game с использованием DAWG - PullRequest
Новая
       81

Поиск предложений по реализации Word Game с использованием DAWG

0 голосов
/ 29 апреля 2020

Я пытаюсь реализовать небольшую игру по следующим правилам: Учитывая набор случайных букв (например, 10), я хочу найти все возможные слова, которые можно составить из этих букв. Для этого я использую стандартный словарь.

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

Например Буквы даны: qrbdtes Возможные слова: bedders, десерт, et c.

В При поиске структуры данных, поддерживающей O (1), для проверки, есть ли предложенное слово в словаре, я нашел эту бумагу , а затем также нашел работающую Java DAWG реализацию здесь .

Вот где я застрял: Когда я пытаюсь составить список возможных слов, которые можно создать из этих букв, я задаюсь вопросом, не упустил ли я что-то, используя реализацию DAWG. Я видел другие потоки, которые предлагают использовать Tr ie и рекурсивно go через узлы, но я надеялся, что смогу сделать что-то подобное с DAWG.

Реализация, над которой я сейчас работаю, состоит в том, чтобы просмотреть все слова словаря, а затем пропустить любое слово, которое содержит букву, НЕ являющуюся частью ранее назначенных букв. Это работает, но медленно, просматривая все слова из словаря * ~ 20 букв наихудшего случая. 

for(String word : dawg.getAllStrings()) {
     boolean blacklist = false;
     for(int i = 0; i<nonLetters.length(); i++) {
         if(word.indexOf(nonLetters.charAt(i)) >= 0) {
             blacklist = true;
             break;
         }
     }

     if(!blacklist)
         possibleWordList.add(word);
}

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

Без доступа к узлу я могу использовать dawg.contains (letter), но с требованием использовать буквы несколько раз, мне интересно, действительно ли это поможет , Например, я бы начал с «А», затем «АА»,… останавливаясь, например, на 20 А.

Будет ли все это проще с Tr ie? Все еще довольно быстро находить подходящие слова, но проще генерировать список возможных слов?

Существуют ли другие библиотеки DAWG, которые предоставляют обход Node или имеют реализацию ref для генерации всех возможных слов?

Спасибо за любую помощь или указатели!

Ответы [ 2 ]

0 голосов
/ 02 мая 2020

Я думаю, что это хороший способ. Я добавил рекурсивный метод в ModifiableDAWGSet реализации DAWG, на которую есть ссылка в вопросе.

getWords вызывается с префиксом String, добавляя символы. Сначала я реализовал это для генерации всех слов в DAWG и сравнил с существующим методом ModifiableDAWGSet.getAllStrings (). Затем я добавил, чтобы пропустить слова, которые не содержат слов, не включая символы из списка возможных символов. 

private ArrayList<String> allMatchingWords = new ArrayList<String>();
private ArrayList<Character> possibleCharacters;

private void getWords(ModifiableDAWGNode originNode, String prefix) {
    NavigableMap<Character, ModifiableDAWGNode> transitionTreeMap = originNode.getOutgoingTransitions();

    for(Map.Entry<Character, ModifiableDAWGNode> transition : transitionTreeMap.entrySet())
    {
        Character c = transition.getKey();
        if(!possibleCharacters.contains(c))
            continue;

        ModifiableDAWGNode n = transition.getValue();
        if(n.isAcceptNode()) //this is a word
        {
            allMatchingWords.add(prefix + c);
        }
        getWords(n, prefix + c);
    }
}

public ArrayList<String> getAllMatchingWords(Character mustContain, ArrayList<Character> possibleCharacters)
{
    this.mustContain = mustContain;
    this.possibleCharacters = possibleCharacters;
    getWords(sourceNode, "");
    return allMatchingWords;
}
0 голосов
/ 29 апреля 2020

У меня есть идея, я не уверен, но надеюсь помочь вам. Сначала создайте словарь как рабочий ключ, ключом будут все буквы, которые слово содержит в алфавитном порядке. Пример: classi c -> acils, letter -> elrt. Аналогично для случайной строки. Вы можете подготовить это для вашей программы. И получите все необходимое для просмотра словаря со сложностью O (n) 

for(Word word : dawg.getAllStrings()){
    if(randomString.contains(word.getKey()))
    possibleWordList.add(word);
}
...