Repository files navigation

This is an implementation of the AhoCorasick efficient string matcher (https://dl.acm.org/doi/10.1145/360825.360855) and Ukkonens' linear time approximate shortest common superstring finder (https://link.springer.com/article/10.1007/BF01840391).

Originally inspired by IMCs 32BIDS coding challenge (already finished), where I implemented the initial version, I decided to clean up and publish my code (under a MIT license).

Both algorithms can be used independently; you can find usage examples either in the tests or in the javadoc. Should you need to build a new algorithm based on ACs' string matcher, you can create a new node extending ACTrieNode and a corresponding implementation of an AbstractACNodeFactory which you then can inject into the AhoCorasickTrieFactory.

You can run the Build with "mvn package". This will run and execute the tests, generate the docs and produce a jar.

Find SCS (Ukkonen):

List<String>keys =List.of("aki","ele","kiki","kira","lea");UkkonenSCSFinderfinder =UkkonenSCSFinder.createFromKeys(keys);Stringscs =finder.getSCS();

Find all matches of a set of keys in a text (AC):

KeywordTextMatchermatcher =KeywordTextMatcher.createFromParameters(LanguageParameterFactory.defaultParameter,keys);List<Match>matches =matcher.matchText(text);

The class LanguageParameter is a utility class which encodes language information. In particular, it stores the characters that embody the aphabet, as well as a mapper function between the characters inside and the integers from 0 (inclusive) to the total alphabet size (exclusive). We need this mapping function because our nodes have a "goto" function that is basically an array linking our current nodes with successor nodes. The successor node in the trie for character c can be found by accessing gotoArray(mapped(c)). In the aftermath, it might have been easier to replace the array with a HashMap, but for small alphabets an array encoding is faster. Nonetheless, the LanguageParameter class pops-up all over the place in my implementation; so it is important to be aware of it.

Create a new LanguageParameter: (from Alphabet alone)

privatestaticfinalList<Character>lowerCaseEnglishAlphabet ="abcdefghijklmnopqrstuvwxyz".chars().mapToObj(c -> (char)c).collect(Collectors.toList());LanguageParameterenglishLowerCaseLanguageParameter =LanguageParameterFactory.createLanguageParametersFromAlphabet(lowerCaseEnglishAlphabet);

Create a new LanguageParameter: (from Alphabet + Custom Mapping Function)

LanguageParameterenglishLowerCaseLanguageParameter =LanguageParameterFactory.createLanguageParametersFromParams(myChar -> (int) (myChar -'a'),lowerCaseEnglishAlphabet);