Java реализация алгоритма сопоставления строк Aho-Corasick?

Question

Java реализация алгоритма сопоставления строк Aho-Corasick?

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

Поэтому для целей собеседования я планировал установить и реализовать алгоритм, используя другой подход.

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

Поэтому, пожалуйста, просветите нас своей мудростью.

Я в основном делаю алгоритм, основанный на этой информации Intuition behind the Aho-Corasick string matching algorithm

Было бы большим бонусом, если бы здесь можно было реализовать собственное решение.

Но вот следующее неполное и не рабочее решение, в котором я действительно застрял:

Если ваш код перегружен, основная проблема заключается в основном алгоритме Aho-Corasick. Мы уже создали три дерева словарей.

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

Ни один из ресурсов не был полезен.

public class DeterminingDNAHealth {
  private Trie tree;
  private String[] dictionary;
  private Node FailedNode;


  private DeterminingDNAHealth() {

  }

  private void buildMatchingMachine(String[] dictionary) {
    this.tree = new Trie();
    this.dictionary = dictionary;

    Arrays.stream(dictionary).forEach(tree::insert);

  }

  private void searchWords(String word, String[] dictionary) {

    buildMatchingMachine(dictionary);

    HashMap < Character, Node > children = tree.parent.getChildren();

    String matchedString = "";

    for (int i = 0; i < 3; i++) {
      char C = word.charAt(i);

      matchedString += C;

      matchedChar(C, matchedString);

    }

  }

  private void matchedChar(char C, String matchedString) {


    if (tree.parent.getChildren().containsKey(C) && dictionaryContains(matchedString)) {

      tree.parent = tree.parent.getChildren().get(C);

    } else {

      char suffix = matchedString.charAt(matchedString.length() - 2);

      if (!tree.parent.getParent().getChildren().containsKey(suffix)) {
        tree.parent = tree.parent.getParent();

      }


    }
  }

  private boolean dictionaryContains(String word) {

    return Arrays.asList(dictionary).contains(word);

  }


  public static void main(String[] args) {

    DeterminingDNAHealth DNA = new DeterminingDNAHealth();

    DNA.searchWords("abccab", new String[] {
      "a",
      "ab",
      "bc",
      "bca",
      "c",
      "caa"
    });


  }
}

Я настроил структуру данных Trie, которая работает нормально. Так что нет проблем здесь

trie.java

public class Trie {
  public Node parent;
  public Node fall;

  public Trie() {
    parent = new Node('⍜');
    parent.setParent(new Node());
  }

  public void insert(String word) {...}

  private boolean delete(String word) {...}

  public boolean search(String word) {...}

  public Node searchNode(String word) {...}

  public void printLevelOrderDFS(Node root) {...}

  public static void printLevel(Node node, int level) {...}

  public static int maxHeight(Node root) {...}

  public void printTrie() {...}

}

То же самое для узла.

Node.java

public class Node {

  private char character;
  private Node parent;
  private HashMap<Character, Node> children = new HashMap<Character, Node>();
  private boolean leaf;

  // default case
  public Node() {}

  // constructor accepting the character
  public Node(char character) {
    this.character = character;
  }

  public void setCharacter(char character) {...}

  public char getCharacter() {...}

  public void setParent(Node parent) {...}

  public Node getParent() {...}

  public HashMap<Character, Node> getChildren() {...}

  public void setChildren(HashMap<Character, Node> children) {...}

  public void resetChildren() {...}

  public boolean isLeaf() {...}

  public void setLeaf(boolean leaf) {...}
}

3

java algorithm data-structures trie aho-corasick

Источник

user7947407 24 окт '17 в 23:01

2 ответа

Решение

Вы не сможете понять алгоритм сопоставления строк Aho-Corasick, прочитав некоторый исходный код. И вы не найдете тривиальной реализации, потому что алгоритм нетривиален.

Оригинальная статья " Эффективное сопоставление строк: помощь в библиографическом поиске" хорошо написана и вполне доступна. Я предлагаю вам скачать этот PDF, внимательно его прочитать, немного подумать и прочитать еще раз. Изучите статью.

Вы также можете прочитать полезные описания алгоритма. Есть много, много страниц с текстовыми описаниями, диаграммами, слайдами Powerpoint и т. Д.

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

Если вам нужен код, есть хорошая реализация: https://codereview.stackexchange.com/questions/115624/aho-corasick-for-multiple-exact-string-matching-in-java.

5

Источник

user56778 25 окт '17 в 15:21

Другие вопросы по тегам java algorithm data-structures trie aho-corasick

user501557 25 окт '17 в 17:32 2017-10-25 17:32 · Accepted Answer · 2017-10-25 17:32

Я обычно преподаю курс по сложным структурам данных раз в два года, и мы рассматриваем автоматы Aho-Corasick при изучении структур строковых данных. Здесь есть слайды, которые показывают, как разработать алгоритм путем оптимизации нескольких более медленных.

Вообще говоря, я бы разбил реализацию на четыре этапа:

Построй три. По своей сути, автомат Aho-Corasick представляет собой три с добавлением некоторых дополнительных стрелок. Первым шагом алгоритма является построение этого три, и хорошая новость заключается в том, что это происходит так же, как и обычная конструкция трии. На самом деле, я бы порекомендовал просто выполнить этот шаг, притворившись, что вы просто делаете трюк, и ничего не делая, чтобы предвидеть последующие шаги.
Добавить суффикс (провал) ссылки. Этот шаг в алгоритме добавляет важные ссылки сбоев, которые использует средство сопоставления всякий раз, когда сталкивается с символом, который он не может использовать, чтобы следовать по краю дерева. Лучшее объяснение, которое я имею, о том, как они работают, находится на связанных слайдах лекций. Этот шаг алгоритма реализован как поиск в ширину по дереву. Прежде чем писать код, я бы порекомендовал проработать несколько примеров вручную, чтобы убедиться, что вы получили общий шаблон. Как только вы это сделаете, это не особенно сложно для кодирования. Однако, попытка закодировать это без полного понимания того, как это работает, сделает отладку кошмаром!
Добавьте выходные ссылки. На этом шаге вы добавляете ссылки, которые используются для отчета обо всех строках, которые соответствуют данному узлу в дереве. Он реализован посредством второго поиска в ширину по всему дереву, и опять же, лучшее объяснение того, как это работает, - это слайды. Хорошая новость заключается в том, что этот шаг на самом деле гораздо проще реализовать, чем создание суффиксной ссылки, поскольку вы будете лучше знакомы с тем, как создавать BFS, и как переходить вверх и вниз по дереву. Опять же, не пытайтесь закодировать это, если вы не можете сделать это вручную! Вам не нужен минимальный код, но вы не хотите зацикливаться на отладочном коде, высокоуровневое поведение которого вы не понимаете.
Реализуйте совпадение. Этот шаг не так уж и плох! Вы просто идете вниз по три, читая символы с входа, выводя все совпадения на каждом шаге и используя ссылки на ошибки, когда вы застряли и не можете продвинуться вниз.

Я надеюсь, что это даст вам более модульную разбивку задач и справку о том, как весь процесс должен работать. Удачи!