Пример реализации алгоритма Ахо-Корасика на Java.
При реализации использовался следующий материал:
- https://e-maxx.ru/algo/aho_corasick
- https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE-%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA
Данный алгоритм был опробован на задаче: https://www.hackerrank.com/challenges/determining-dna-health/problem
Пример использования:
List<AhoCorasick.Entry> entryList = new ArrayList<>(); List<String> list = Arrays.asList("b", "c", "aa", "d", "b"); for (String s : list) { AhoCorasick.Entry entry = new AhoCorasick.Entry(); entry.setValue(s); entryList.add(entry); } AhoCorasick ahoCorasick = new AhoCorasick(entryList, 26); ahoCorasick.solve("caaab"); |
Сама реализация алгоритма:
import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Реализация алгоритма Ахо-Корасика */ public class AhoCorasick { private List<Entry> entryList; private int alphabetSize; private List<Vertex> vertexList; private int vertexCount; public AhoCorasick(List<Entry> entryList, int alphabetSize) { this.entryList = entryList; this.alphabetSize = alphabetSize; } // Строка набора public static class Entry { private String value; public String getValue() { return value; } public void setValue(String value) { this.value = value; } @Override public String toString() { return "Entry{" + "value='" + value + '\'' + '}'; } } // Вершина бора (состояние конечного детерминированного автомата) public static class Vertex { private int next[]; // массив сыновей private boolean isLeaf; // терминальная вершина private int parent; // родительская вершина private int charIndexFromParent;// символ перехода от родителя private int suffixLink; // суффиксная ссылка private int go[]; // массив переходов, используемый для вычисления суффиксных ссылок public Vertex(int alphabetSize) { this.next = newIntArray(alphabetSize); this.go = newIntArray(alphabetSize); this.parent = -1; this.suffixLink = -1; } private int[] newIntArray(int size) { int[] ints = new int[size]; Arrays.fill(ints, -1); return ints; } @Override public String toString() { return "Vertex{" + "next=" + Arrays.toString(next) + ", go=" + Arrays.toString(go) + ", isLeaf=" + isLeaf + '}'; } } public List<Entry> getEntryList() { return entryList; } // добавить строку в набор public boolean addEntry(Entry entry) { return entryList.add(entry); } // поиск всех строк из заданного набора в тексте public void solve(String text) { vertexList = new ArrayList<>(); vertexList.add(new Vertex(alphabetSize)); vertexList.add(new Vertex(alphabetSize)); vertexCount = 1; for (Entry entry : entryList) { addToTrie(entry); } int v = 0; for (char ch : text.toCharArray()) { v = go(v, charToIndex(ch)); Vertex vertex = vertexList.get(v); if(vertex.isLeaf) { // посещение терминальной вершине - это нахождение строки из заданного набора System.out.println(v + " " + vertex); } } } // добавить в бор private void addToTrie(Entry entry) { int v = 0; for (char ch : entry.value.toCharArray()) { int sym = charToIndex(ch); if(vertexList.get(v).next[sym] == -1) { Vertex vertex = vertexList.get(vertexCount); vertex.suffixLink = -1; vertex.parent = v; vertex.charIndexFromParent = sym; vertexList.add(new Vertex(alphabetSize)); vertexList.get(v).next[sym] = vertexCount++; } v = vertexList.get(v).next[sym]; } vertexList.get(v).isLeaf = true; } private int charToIndex(char ch) { return ch - 'a'; } // обычный переход private int go(int v, int sym) { Vertex vertex = vertexList.get(v); if(vertex.go[sym] == -1) { if(vertex.next[sym] != -1) { vertex.go[sym] = vertex.next[sym]; } else { vertex.go[sym] = v == 0 ? 0 : go(goBySuffixLink(v), sym); } } return vertex.go[sym]; } // переход по суффиксной ссылке (к вершине, в которой оканчивается наидлиннейший собственный суффикс строки) private int goBySuffixLink(int v) { Vertex vertex = vertexList.get(v); if(vertex.suffixLink == -1) { if(v == 0 || vertex.parent == 0) { vertex.suffixLink = 0; } else { vertex.suffixLink = go(goBySuffixLink(vertex.parent), vertex.charIndexFromParent); } } return vertex.suffixLink; } } |