Приговор Три / Дерево / словарь / корпус - PullRequest
Новая
       28

Приговор Три / Дерево / словарь / корпус

0 голосов
/ 18 мая 2018

Я надеюсь построить дерево, в котором узел - это английское слово, а ветвь листьев образует предложение.А именно, дерево предложений (пожалуйста, игнорируйте числа):

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

Имеет ли это смысл?Я открыт для других структур данных.Цель состоит в том, чтобы создать словарь / корпус, в котором будет храниться множество английских предложений.Пользователи могут использовать первые пару слов, чтобы найти все предложение.Я самый опытный в Java, но я также знаю Python и R, так что если их будет проще использовать для моих целей.

Спасибо! 

void insert(String key) {
    int level;
    int length = key.length();
    int index;

    TrieNode pCrawl = root;

    for (level = 0; level < length; level++)
    {
        index = key.charAt(level) - 'a';
        if (pCrawl.children[index] == null)
            pCrawl.children[index] = new TrieNode();

        pCrawl = pCrawl.children[index];
    }

    // mark last node as leaf
    pCrawl.isEndOfWord = true;
}

1 Ответ

0 голосов
/ 22 августа 2018

Немного поздно, но, может быть, я могу немного помочь даже сейчас.

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

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

На каждом уровне вашего трия вы смотрите на следующее слово и ищите его позицию в списке детей, а не смотрите на следующий символ.К сожалению, все традиционные реализации показывают сортировку по символам.

У меня есть решение, а точнее два.Во-первых, используйте мой исходный код Java trie .Это сортирует любой объект (в вашем случае строку, содержащую ваше предложение) по Перечислению целых чисел.Вам нужно будет сопоставить ваши слова с целыми числами (хранить слова в три, дать каждому уникальное число), а затем написать перечислитель, который возвращает wordIntegers для предложения.Это будет работать.(Не используйте хэш для преобразования слова -> целое число, так как два слова могут дать одинаковый хэш).

Второе решение - взять мой код и вместо сравнения целых чисел сравнивать слова как строки.Это займет больше работы, но выглядит вполне выполнимо.На самом деле у меня было подозрение, что мое решение можно сделать более общим, заменив Enumeration of Integer на Enumeration of Comparable.Если вы хотите сделать это или сотрудничать в этом, мне было бы интересно.Черт возьми, я могу даже сделать это сам для удовольствия.

Результирующий три будет иметь универсальный тип 

Trie<K extends Comparable, T>

и будет хранить экземпляры T против последовательности K. Кодерпотребуется определить метод 

Iterator<K extends Comparable> getIterator(T t)

============================ РЕДАКТИРОВАТЬ: ========================

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

SentenceSorter sorter = new SentenceSorter();
sorter.add("This is a sentence.");
sorter.add("This is another sentence.");
sorter.add("A sentence that should come first.");
sorter.add("Ze last sentence");
sorter.add("This is a sentence that comes somewhere in the middle.");
sorter.add("This is another sentence entirely.");

Затем перечислю предложения по: 

Iterator<String> it = sorter.iterator();
while (it.hasNext()) {
    System.out.println(it.next()); 
}

дает 

A sentence that should come first.
This is a sentence that comes somewhere in the middle.
This is a sentence.
This is another sentence entirely.
This is another sentence.

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

Мы можем показать, что мы сортируем по словам, а не по символам: 

it = sorter.sentencesWithPrefix("This is a").iterator();
while (it.hasNext()) {
    System.out.println(it.next()); 
}

дает 

This is a sentence that comes somewhere in the middle.
This is a sentence.

, тогда как 

it = sorter.sentencesWithPrefix("This is another").iterator();
while (it.hasNext()) {
    System.out.println(it.next()); 
}

дает 

This is another sentence entirely.
This is another sentence.

Надеюсь, что это поможет - код полностью включен в вышеупомянутый репозиторий и свободно доступен под Apache2.

...