Реализация дерева суффикса в Java

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

Мой SuffixTree по существу является Узлом, который содержит значение и Map из <Character,Node> для своих детей.

import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class SuffixTree{
 class Node{
   private final char currentValue;
   private Map<Character,Node> children;
   Node(){
     this.currentValue = '*';
     this.children = new HashMap<Character,Node>();
   }    
   Node(char currentValue){
     this.currentValue = currentValue;
     this.children = new HashMap<Character,Node>();
   }       

   char getValue(){
     return this.currentValue;
   }

   void addChild(Node c){
    this.children.put(c.getValue(),c);
   }

   boolean hasChild(Node c){
    return this.children.containsKey(c.getValue());
   }  

   Node getChild(Node c){
     return this.children.get(c.getValue());
   }

  public String toString(){
    char currentValue = this.getValue();
    StringBuffer keys = new StringBuffer();
    for(char key:this.children.keySet()){
      keys.append("Current key:"+key+"\n");
    }
     return "Current value:"+currentValue+"\n"+
        "Keys:"+keys.toString(); 
   }
  }  

  private Node root;

  private void log(Object l){
     System.out.println(l);
  }
  /*
   * Helper method that initializes the suffix tree
   */
  private Node createSuffixTree(String source,Node root){
    for(int i=0;i<source.length();i++){
      Node parent = new Node(source.charAt(i));
      if(root.hasChild(parent)){
        parent = root.getChild(parent);
      }
      Node current = parent;            
      for(int j=i+1;j<source.length();j++){
        Node temp = new Node(source.charAt(j));
    if(current.hasChild(temp)){
      temp = current.getChild(temp);
    }else{
      current.addChild(temp);
    }
        current = temp; 
      }
      root.addChild(parent);    
    }
    return root;         
  }

  /*
   Creates the suffix tree from the given string
   */
  public SuffixTree(String source){
    this.root = createSuffixTree(source,new Node());
  }   

  void printMap(Map<Character,Node> map){
     for(char c:map.keySet()){
      System.out.println("Current node has child"+c);
    }
  }  

  boolean search(String target){
    Map<Character,Node> rootChildren = this.root.children;
   for(char c:target.toCharArray()){
      if(rootChildren.containsKey(c)){
        rootChildren = rootChildren.get(c).children;
      }else{
        return false;
      }
    }
    return true;
  }

   public static void main(String[] args){
    SuffixTree sTree = new SuffixTree("bananas");
    List<String> input = new ArrayList<String>(){{
                 add("ba");
                 add("ban");
                 add("ana");
                 add("anas");
                 add("nan");
                 add("anans");
                 add("ananas");
                 add("n");
                 add("s");
                 add("as");
                 add("naab");
                 add("baan");
                 add("aan");
                }};
    for(String i:input){
      String exists = "exists";
      if(!sTree.search(i)){
        exists = "doesn't exist";
      }
      System.out.println("Input:"+i+" "+exists);
    }
   }
}
12 голосов | спросил sc_ray 18 PMpSat, 18 Apr 2015 22:49:34 +030049Saturday 2015, 22:49:34

3 ответа


11

Давайте сломаем ваш алгоритм на мгновение:

  1. получить строку для анализа («бананы»).
  2. выполните «вложенный» цикл (i, j), чтобы найти в нем все возможные подсловы
  3. для каждого подслова, введите его в возможное дерево узла по одному символу за раз.

С помощью этого дерева вы можете сравнить совпадающие значения, чтобы увидеть, существуют ли они в дереве. Чтобы узнать, существуют ли они, вы:

  1. цикл над каждым символом в поисковом слове
  2. для каждого символа, вы проверяете, существует ли узел, соответствующий соответствующему символу a соответствующего уровня.
  3. Если какой-либо символ невозможен, вы возвращаете false. Если все символы возможны, вы возвращаете true.

Проблемы

  1. имя - это не дерево «Суффикс», это дерево «Infix». Он не соответствует только суффиксам.
  2. Накладные расходы - экземпляры HashMap и классы символов и узлов - проблема с точки зрения памяти. Конечно, количество этих экземпляров будет относительно небольшим, но для «бананов» вы создаете около ... 28 HashMaps? Каждый HashMap имеет значительный объем памяти. Это дорого.

Преимущества

  1. Предполагаемое преимущество заключается в том, что у вас есть отдельные места, где данные существуют в дереве. Вы можете одновременно проверять инфикс, начиная с любого символа в базовом слове.

Альтернативы

Есть две альтернативы, которые я рекомендую, различия между ними будут зависеть от количества букв во входном слове. Одно решение имеет производительность выполнения \ $ O (1) \ $, но потребление памяти \ $ O (n ^ 2) \ $. Другая имеет производительность выполнения \ $ O (n \ log n) \ $ и потребление памяти \ $ O (n) \ $. Обратите внимание, что ваше решение имеет производительность выполнения \ $ O (n) \ $ и размер памяти \ $ O (n ^ 2) \ $.

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

В вашем решении, когда \ $ n \ $ является числом букв во входном слове («бананы»), ваша производительность во время выполнения требует сканирования дерева узлов для целых n узлы (по одному для каждой буквы), что делает эффективность проверки пропорциональной количеству символов во входном слове. Количество узлов, которые у вас есть, пропорционально квадрату числа входных букв, поэтому, если вы удваиваете количество букв, вы в четыре раза увеличиваете количество узлов.

Две альтернативы, которые я предлагаю, различны, поскольку одна альтернатива будет иметь производительность \ $ O (n \ log n) \ $ поиска, но производительность памяти \ $ O (n) \ $. Однако из-за того, что хранятся данные, для небольших входных строк («бананы» малы), скорее всего, это будет намного быстрее, чем ваш.

Другое решение намного быстрее (по существу постоянное время - \ $ O (1) \ $), но имеет более высокую стоимость памяти - примерно то же, что и ваш код.

Самый быстрый - и самый большой

Самое быстрое решение - взять все возможные подстроки из ввода и поместить их в код HashSet. Обработка ввода проста:

Set<String> infixes = new HashSet<>();
for (int i = 0; i < input.length; i++) {
    for (j = i + 1; j < input.length; j++) {
        infixes.add(input.substring(i,j));
    }
}

Теперь есть один HashSet (который под обложками - HashMap), и он содержит все подстроки. Поиск этих подстрок - это случай вычисления хэш-кода значения поиска, и он найдет значение «fast» ...

return infixes.contains(search);

Этот алгоритм хранит потенциально много строк, но поиск молниеносно.

Способ, которым работает этот код, заключается в том, что он принимает входную строку и разбивает ее всеми возможными способами. Например, из «fubar» вы получите:

f fu fub fuba fubar u ub uba ubar b ba bar a ar r

Поместите все в набор, и записывается каждое возможное слово поиска «infix». HashSet эффективно выполняет поиск O (1)операции.

Fastish - и Smallish

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

Сначала создайте массив слов ... каждое слово будет суффиксом:

String[] suffixes = new String[input.length];
for (int i = 0; i < input.length; i++) {
    suffixes[i] = input.substring(i);
}

Затем, отсортируйте его ....

Arrays.sort(suffixes);

Этот массив довольно мал по сравнению с вашими альтернативами.

Теперь, используя это, вы можете быстро найти (в \ $ O (n \ log n) \ $ time), является ли строка поиска суффиксом:

int ip = Arrays.binarySearch(suffixes, search);
if (ip >= 0) {
    // exact match to a suffix
    return true;
}
// no exact match, but, maybe the place the value would
// belong is a longer version of our search term....
ip = -ip - 1;

return ip < suffixes.length && suffixes[ip].startsWith(search);

Этот алгоритм частично работает, опираясь на лексическую (алфавитную) сортировку любого суффикса входного слова. Опять же, используя «fubar», код создает все 5 суффиксов:

fubar ubar bar ar r

Затем он сортирует их по алфавиту:

ar
bar
fubar
r
ubar

Теперь, если вы хотите найти строку поиска, которая является полным суффиксом (например, «bar»), тогда двоичный поиск не обнаружит проблем и вернет true. Но, что, если вы хотите, чтобы вы заработали «инфикс» или неполный суффикс, например, «ba»? Ну, «ba» обычно вписывается в алфавитном порядке между «ar» и «bar». Arrays.binarySearch вернет« точку вставки » -2. Параметр -2 указывает, что не было точного соответствия, но если мы хотим вставить значение в массив, мы должны вставить его перед элементом в - ip - 1, или, поскольку ip является -2, at - (-2) - 1, или до позиции 1.

Обратите внимание, что из-за алфавитного порядка, если поисковый термин является инфиксным, он по определению является префиксом суффикса ;-), и если он является префиксом суффикса, то суффикс это префикс алфавита сразу после него. Таким образом, если поисковый термин соответствует началу значения точки вставки, то термин поиска является инфикс исходного слова.

Это всего лишь сложный способ сказать: если поисковый термин является точным совпадением суффикса, он является совпадением или, если он соответствует началу суффикса по алфавиту после него, это соответствие.

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

код

public class SearchNLogN {

    private final String[] suffixes;

    public SearchNLogN(String input) {
        suffixes = new String[input.length()];
        for (int i = 0; i < suffixes.length; i++) {
            suffixes[i] = input.substring(i);
        }
        Arrays.sort(suffixes);
    }

    public boolean search(final String search) {
        int ip = Arrays.binarySearch(suffixes, search);
        if (ip >= 0) {
            return true;
        }
        ip = -ip - 1;
        return ip < suffixes.length && suffixes[ip].startsWith(search);
    }

}

и

import java.util.HashSet;
import java.util.Set;

public class SearchO1 {

    private final Set<String> infixes = new HashSet<>();

    public SearchO1(String input) {
        for (int i = 0; i < input.length(); i++) {
            for (int j = i + 1; j <= input.length(); j++) {
                infixes.add(input.substring(i, j));
            }
        }
    }

    public boolean search(String search) {
        return infixes.contains(search);
    }

}

Результаты

Запуск двух фрагментов кода выше, а также фрагмента кода для ряда значений iunput («foo», «bananas» и «supercali ......»), с рядом тестовых значений (включая само входное значение), а затем сравнивая результаты (используя Microbench ), я получаю:

Ваш код: маленький, средний, большой (микросекунды) - 0,24, 0,5, 1,2

Task SuffixTree -> foo: (Unit: MICROSECONDS)
  Count    :     10000      Average  :    0.5620
  Fastest  :    0.2390      Slowest  : 1044.6770
  95Pctile :    0.7730      99Pctile :    1.2420
  TimeBlock : 1.480 0.471 0.326 0.271 0.257 0.254 0.263 0.249 0.252 1.804
  Histogram :  8781   855   302    11     1    44     2     1     1     0     0     1     1

Task SuffixTree -> bananas: (Unit: MICROSECONDS)
  Count    :     10000      Average  :    0.9490
  Fastest  :    0.5020      Slowest  : 1107.9860
  95Pctile :    1.7720      99Pctile :    2.7260
  TimeBlock : 2.734 0.848 0.670 0.635 0.532 0.635 0.635 0.612 1.638 0.561
  Histogram :  8790   870   268    13    12    41     0     5     0     0     0     1

Task SuffixTree -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   1.8380
  Fastest  :   1.2400      Slowest  :  96.8740
  95Pctile :   3.8860      99Pctile :   5.9270
  TimeBlock : 5.778 1.999 1.392 1.321 1.300 1.337 1.315 1.276 1.301 1.371
  Histogram :  8782  1082    51    44    24    16     1

Поиск O1: маленький, средний, большой (микросекунды) - 0,18, 0,25, 0,21

Task SearchO1 -> foo: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.7840
  Fastest  :   0.1810      Slowest  :  75.3810
  95Pctile :   1.9970      99Pctile :   2.5670
  TimeBlock : 2.212 2.002 1.980 0.255 0.236 0.250 0.236 0.228 0.225 0.226
  Histogram :  6978     3     3  2944    46    12    13     0     1

Task SearchO1 -> bananas: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.9330
  Fastest  :   0.2510      Slowest  :  36.0610
  95Pctile :   2.2400      99Pctile :   3.1790
  TimeBlock : 2.429 2.231 2.284 0.367 0.343 0.356 0.346 0.340 0.318 0.316
  Histogram :  6969     3   243  2735    19    28     1     2

Task SearchO1 -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.8450
  Fastest  :   0.2190      Slowest  :  21.3880
  95Pctile :   2.1300      99Pctile :   2.6750
  TimeBlock : 2.208 2.120 2.104 0.309 0.290 0.297 0.291 0.279 0.279 0.276
  Histogram :  6966    13    29  2955    23    13     1

Поиск NlogN: маленький, средний, большой (микросекунды) - 0,24, 0,33, 0,60

Task SearchNLogN -> foo: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.5180
  Fastest  :   0.2430      Slowest  :  66.9210
  95Pctile :   1.0680      99Pctile :   2.2020
  TimeBlock : 1.430 0.350 0.252 0.357 0.504 0.504 0.550 0.531 0.392 0.312
  Histogram :  5928  3500   389   128    20    29     4     1     1

Task SearchNLogN -> bananas: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   0.6610
  Fastest  :   0.3340      Slowest  :  44.2550
  95Pctile :   1.2930      99Pctile :   2.5630
  TimeBlock : 1.671 0.429 0.350 0.497 0.678 0.675 0.705 0.688 0.542 0.384
  Histogram :  6812  2758   342    48    25     9     5     1

Task SearchNLogN -> supercalifragilisticexpialidocious if you like the sounds of that it must be quite atrocious.: (Unit: MICROSECONDS)
  Count    :    10000      Average  :   1.1370
  Fastest  :   0.6030      Slowest  :  46.9750
  95Pctile :   1.9280      99Pctile :   4.7460
  TimeBlock : 2.719 0.737 0.628 0.887 1.187 1.194 1.204 1.216 0.924 0.679
  Histogram :  8380  1266   256    57    34     6     1
ответил rolfl 22 PMpWed, 22 Apr 2015 15:28:54 +030028Wednesday 2015, 15:28:54
5

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

Если цель состоит в том, чтобы проверить, содержит ли более длинную строку каждую более короткую строку из списка, почему бы просто не использовать класс String, встроенный содержит () метод?

public class StringUtil {

    public static void main(String[] args){
        String input = "bananas";
        List<String> substrings = new ArrayList<String>(){{
                 add("ba");
                 add("ban");
                 add("ana");
                 add("anas");
                 add("nan");
                 add("anans");
                 add("ananas");
                 add("n");
                 add("s");
                 add("as");
                 add("naab");
                 add("baan");
                 add("aan");
                }};
        if(StringUtil.containsAllSubstrings(input, substrings)) {
            System.out.println("Input: \"" + input + "\" contains all substrings.");
        } else {
            System.out.println("Input: \"" + input + "\" does not contain all substrings.");
        }
    }

    public static Boolean containsAllSubstrings( String input, List<String> substrings) {
        for(String substring : substrings) {
            if(!input.contains(substring)) {
                return false;
            }
        }
        return true;
    }
}
ответил Łukasz Ciosek 19 PMpSun, 19 Apr 2015 19:29:01 +030029Sunday 2015, 19:29:01
3

Существует много жира, подлежащего обрезке, главным образом из-за неэффективного внутреннего класса Node. Это решение функционально эквивалентно:

import java.util.HashMap;

public class SuffixTree {
    private static class Node extends HashMap<Character, Node> {
        /**
         * Follows a link to get a child node.  If no such link
         * exists, then create and attach an empty child node.
         */
        Node getOrPut(char c) {
            Node child = this.get(c);
            if (child == null) {
                this.put(c, child = new Node());
            }
            return child;
        }
    }

    private Node root;

    /**
     * Creates the suffix tree from the given string.
     */
    public SuffixTree(CharSequence source) {
        this.root = new Node();
        for (int i = 0; i < source.length(); i++) {
            Node n = this.root.getOrPut(source.charAt(i));
            for (int j = i + 1; j < source.length(); j++) {
                n = n.getOrPut(source.charAt(j));
            }
        }
    }

    public boolean contains(CharSequence target) {
        Node n = this.root;
        for (int i = 0; i < target.length(); i++) {
            n = n.get(target.charAt(i));
            if (n == null) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        SuffixTree sTree = new SuffixTree("bananas");
        String[] input = new String[] {
            "ba",
            "ban",
            "ana",
            "anas",
            "nan",
            "anans",
            "ananas",
            "n",
            "s",
            "as",
            "naab",
            "baan",
            "aan",
        };
        for (String s : input) {
            String exists = sTree.contains(s) ? "exists" : "doesn't exist";
            System.out.printf("Input: %s %s\n", s, exists);
        }
    }
}

Примечания:

  1. Node должен быть статическим внутренним классом , так как ему не нужно ссылаться на SuffixTree, к которому он принадлежит. Внутренние классы должны быть static, когда это возможно.
  2. Я не считаю, что addChild(), hasChild(), а методы getChild() добавляют большую ценность за пределы put(), containsKey() и get() методов Map. В частности, hasChild(Node c) и getChild(Node c) глупы , так как вам нужно сначала построить узел для поиска узла . Как только вы исправите эту неэффективность, вы обнаружите, что поле currentValue бесполезно.
  3. Как только вы отмените поле currentValue, затем Node just is a HashMap . Я добавил метод удобства getOrPut(), чтобы упростить процесс создания дерева суффиксов.
  4. Я не вижу смысла иметь вспомогательную функцию createSuffixTree(). Почему бы просто не поместить этот код в конструктор SuffixTree?
  5. Для общности вы можете принять любой CharSequence, а не только String.
  6. Метод search() должен быть public , иначе в вашем классе нет смысла. Поскольку он возвращает логическое значение, я бы переименовал его в contains() , так что код, который его вызывает, читает больше плавно.
  7. В main(), заполняется input , используя статический блок инициализатора анонимного внутреннего класса, который подклассы ArrayList является излишним. Здесь будет использоваться массив String[]. Если вы действительно нуждались в ArrayList, используйте Arrays.asList("ba", "ban", … ) .
  8. Это лучше написано как тройное выражение:

    String exists = "exists";
    if(!sTree.search(i)){
      exists = "doesn't exist";
    }
    
  9. Ваш отступ не соответствует.
  10. Комментарий к конструктору SuffixTree выглядит как JavaDoc, но это не так. Если вы вообще пишете комментарий, тогда сделайте его действительным JavaDoc.
ответил 200_success 21 AMpTue, 21 Apr 2015 10:06:54 +030006Tuesday 2015, 10:06:54

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

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

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