Выполнение Trie для поиска по шаблону слева направо

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

Конечно, первая и самая легкая реализация - это пройти через каждый элемент и сделать a[i].startWith(query). Технически временная сложность этого алгоритма тогда была бы \ $ O (n + (q * m)) \ $. Здесь n равно количеству элементов в массиве, q равно числу общих совпадений и m равно числу символов в запросе (я не уверен, насколько точно я здесь).

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

Например, если запрос "can", то только с тремя обхода дерево вернет cancel, cancer, can and cancellation, потому что узел 'n' будет иметь подключения ко всем субам, у которых есть слово окончание!

Мне бы очень хотелось услышать некоторые комментарии по этому поводу.

package utils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *
 * @author Sapan
 */
public class Trie {

    private Map<Character, Trie> children;
    private String word = null;
    private Set<Trie> connections;
    static int count = 0;

    public Trie() {
        this.children = new HashMap<>();
        connections = new HashSet<>();
    }
    /*
     * Builds a Trie with given query
     */

    public void add(String word) {
        if (word == null || "".equals(word.trim())) {
            throw new IllegalArgumentException("Query can not be empty or null");
        }
        Trie t = this;
        for (Character c : word.toCharArray()) { //for every character in query do the following....
            //add character to the current instance and get the child instance right after adding the current char
            if (!t.children.containsKey(c)) {
                t.children.put(c, new Trie());
            }
            t = t.children.get(c);
        }
        t.word = word;
    }

    public Set search(String word) {
        count = 0;
        Trie current = this;
        Set<Trie> matches = new HashSet();
        for (Character c : word.toCharArray()) {
            ++count;
            current = current.children.get(c);
            if (current == null){
                return matches;
            }
        }
        //System.out.println(current);
        if (current == null) {
            return matches;
        }

        matches = current.connections;

        return matches;
    }
    public Set build() {
        //matches = new HashSet<>();
        ++count;
        for (Character c : this.children.keySet()) {
            this.connections.addAll(this.children.get(c).build());
        }
         if (this.word != null && this.word.length() > 0) {
             this.connections.add(this);
        }
         if (this.children.keySet().isEmpty()) {// we are at the leaf node
            this.connections.add(this);
        }
        return this.connections;
    }


    public static void main(String[] args) {
        Trie t = new Trie();
        t.add("can");
        t.add("kangaroo");
        t.add("roo");
        t.add("rash");
        t.add("ram");
        t.add("rat");
        t.add("kansas");
        t.add("banana");
        t.add("ban");
        t.add("cancel");
        t.add("cancer");
        t.add("add");
        t.add("addition");
        t.add("sub");
        t.add("subtraction");
        t.add("ape");
        t.add("apple");
       // t.build();
        t.build();
        System.out.println(t);
        System.out.println(t.count+"----");
        //System.out.println(t);
       // List<Trie> l = t.search("ap");

        //System.out.println(l);
       // for (char c = 'a'; c <= 'z'; c++) {
           Set<Trie> l = t.search("ca");
           System.out.println(t.count);
            System.out.println("words starting from ca ");
            for (Trie trie : l) {
                System.out.println(trie.word);
            }
    }
}
11 голосов | спросил Grrrrr 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 25 Sep 2012 01:09:34 +0400 2012, 01:09:34

1 ответ


8
  1. Eclipse говорит, что второй null проверьте search - мертвый код:

    if (current == null) {
        return matches;
    }
    

    Кроме того, он может быть реорганизован следующим образом:

    public Set<Trie> search(final String word) {
        count = 0;
        Trie current = this;
        for (final Character c: word.toCharArray()) {
            ++count;
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return current.connections;
    }
    
  2. Вы должны указать типы возврата:

    public Set<Trie> search(final String word) { ... }
    public Set<Trie> build() {... }
    

    вместо

    public Set search(final String word) { ... }
    public Set build() {... }
    
  3. Рассмотрим использование

    Я нашел их более читаемыми.

  4. Если я прав, вы можете перебирать значения непосредственно в методе build:

    for (final Trie childTrie: children.values()) {
        connections.addAll(childTrie.build());
    }
    
  5. Я отделил бы логику строителя от класса Trie. В настоящее время клиенты могут легко злоупотреблять этим классом:

    t.build();
    t.add("can2");
    

    ( Эффективное Java, второе издание, пункт 2: рассмотрите конструктор, столкнувшись со многими параметрами конструктора )

  6. connections не похоже на хорошее имя. Понадобилось некоторое время, чтобы выяснить, что этот набор содержит объекты-потомки Trie, который имеет word. Я мог бы назвать это descendantsWithWord. Кроме того, он может содержать только слова (строки), а не объекты Trie, поэтому это может быть просто Set<String> descendantWords

  7. Поле static count плохо пахнет. Он используется для двух разных целей. Я бы создал поле createdTrieObjects:

    private int createdTrieObjects = 1;
    

    и добавьте его в метод add:

    t.children.put(c, new Trie());
    createdTrieObjects++;
    

    С другой стороны, в методе search вы можете вернуть SearchResult, который содержит глубину поиска (в настоящее время это count) и строки результата:

    public class SearchResult {
    
        private final Set<String> words;
        private final int searchDepth;
    
        ...
    
    }
    

    Он содержит только набор строк вместо коллекции Set<Trie>. Я думаю, что клиенты не должны знать о внутренних объектах Trie. Если вам не требуется поиск глубины поиска с помощью Set<String>:

    public Set<String> search(final String wordStart) {
        Trie current = this;
        for (final Character c: wordStart.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return Collections.unmodifiableSet(current.descendantWords);
    }
    

    Обратите внимание на вызов Collections.unmodifiableSet. Он запрещает вредоносным клиентам изменять внутреннюю структуру Trie. ( Эффективная Java, 2nd Edition, Item 39: Сделайте защитные копии при необходимости )

  8. Вы можете устранить метод build и word, если вы заполните descendantWords в add:

     public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        Trie current = this;
        descendantWords.add(word);
        for (final Character c: word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Trie());
                createdTrieObjects++;
            }
            current = current.children.get(c);
            current.descendantWords.add(word);
        }
    }
    

Некоторые небольшие заметки о редактировании:

  1. Вместо проверочного IllegalAccessException я бы выбрал runtime IllegalStateException. Это скорее ошибка программирования, если клиент пытается добавить новый элемент в построенное trie. ( Эффективное Java, 2nd Edition, Item 58: Использовать проверенные исключения для восстанавливаемых условий и исключений во время выполнения для ошибок программирования )

  2. О переменной s в search: попытайтесь минимизировать область локальных переменных. Нет необходимости объявлять их в начале метода, объявлять их там, где они впервые используются.( Эффективное Java, второе издание, пункт 45: свести к минимуму область локальных переменных )

  3. Вы можете скопировать код descendantsWithWord с помощью HashSet вместо цикла for в search:

    return new HashSet<String>(current.descendantWords);
    
  4. Флаг isBuilt должен находиться в начале класса с другими полями.

Вот отредактированная версия:

import java.util.Collections;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.apache.commons.lang3.StringUtils;

import static com.google.common.base.Preconditions.*;

public class Trie {

    private final Map<Character, Trie> children = new HashMap<Character, Trie>();
    private final Set<String> descendantWords = new HashSet<String>();

    public Trie() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        Trie current = this;
        descendantWords.add(word);
        for (final Character c: word.toCharArray()) {
            if (!current.children.containsKey(c)) {
                current.children.put(c, new Trie());
            }
            current = current.children.get(c);
            current.descendantWords.add(word);
        }
    }

    public Set<String> search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        Trie current = this;
        for (final Character c: wordStart.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return Collections.emptySet();
            }
        }
        return Collections.unmodifiableSet(current.descendantWords);
    }
}

Изменить комментарий:

В вашей первоначальной реализации есть набор (descendantsWithWord) в каждом узле, который ссылается на Trie. В этом ответе есть набор (descendantWords) на каждом уровне, который ссылается на String.

Размер наборов один и тот же, String s (а также другие объекты, например Trie s) находятся в куче, набор содержит только ссылки на объекты, поэтому он не учитывается, являются ли они String s, Trie s или другой Object s, нет разницы в потреблении памяти и дублирования нет. Единственное отличие - это метод, в котором trie создает набор и общий тип набора (ссылки в наборе).

Я не слишком хорошо знаком с попытками и статьями в Википедии, не упоминает, что три узла должны или не должны хранить каждого потомка (а не только ссылки на узлы следующего уровня), поэтому я не уверен, что это «официально» - это трю или нет.

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

Кроме того, я бы подумал об использовании структуры Map<String, Set<String>>:

c,      [can, cancel, cancer]
ca,     [can, cancel, cancer]
can,    [can, cancel, cancer]
canc,   [cancel, cancer]
cance,  [cancel, cancer]
cancel, [cancel]
cancer, [cancel]
...

Это очень похоже на trie выше, поскольку (1) узлы trie являются такими же, как ключи на этой карте, и (2) значения карты такие же, как descendantWords установлен в trie. Преимуществом может быть более простая реализация, особенно с помощью Multimap из Guava:

public class AutoSuggestCache {

    private final SetMultimap<String, String> words = HashMultimap.create();

    public AutoSuggestCache() {
    }

    public void add(final String word) {
        checkArgument(StringUtils.isNotBlank(word), "word can not be blank");
        for (int endIndex = 0; endIndex < word.length(); endIndex++) {
            final String wordStart = word.substring(0, endIndex);
            words.put(wordStart, word);
        }
    }

    public Set<String> search(final String wordStart) {
        checkNotNull(wordStart, "wordStart cannot be null");
        return Collections.unmodifiableSet(words.get(wordStart));
    }
}
ответил palacsint 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 25 Sep 2012 02:58:41 +0400 2012, 02:58:41

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132