Vor einiger Zeit erfreute ich mich an der Suchfunktion für Klassen in IntelliJ IDEA. Gibt man dort z. B. “arrli” ein, werden die Treffer so gefiltert, dass man relativ schnell auf “ArrayList” kommt. Es werden also Teile der Eingabe an verschiedenen Stellen gesucht, denn das “arr” ist am Anfang von “ArrayList”, das “li” erst in der Mitte. So fasziniert, wie ich von dieser nützlichen Funktion war, wollte ich wissen, wie sie funktioniert.
Gegen meine Erwartung ist hier kein komplexer Wortvergleich Algorithmus tätig, wie etwa Hamming-Distanzen oder Levenshtein-Distanz, sondern ein recht einfaches Prinzip: N-Gramme.
Hierzu werden alle benachbarten Buchstabenkombinationen des Eingabetextes mit N Buchstaben gebildet. Üblicherweise werden vorher alle nicht relevanten Zeichen, wie Leerzeichen oder Satzzeichen entfernt und alle Buchstaben auf klein gestellt.
Das Wort gigacode wird bei N=2 in folgende Zweierblöcke (2-Gramme, Bigramme) zerlegt:
gi
ig
ga
ac
co
od
de
Bei N=3 entstehen analog folgende Blöcke (3-Gramme):
gig
iga
gac
aco
cod
ode
Nun wird für jedes der N-Gramme auch hinterlegt, von welcher Eingabe er stammt:
gi -> gigacode
ig -> gigacode
ga -> gigacode
ac -> gigacode
co -> gigacode
od -> gigacode
de -> gigacode
Wenn wir nun einen weiteren Text, wie “garage” indizieren, sieht der Index wie folgt aus:
gi -> gigacode
ig -> gigacode
ga -> gigacode, garage
ac -> gigacode
co -> gigacode
od -> gigacode
de -> gigacode
ar -> garage
ra -> garage
ag -> garage
ge -> garage
Ein solcher Index lässt sich wunderbar durch eine Map realisieren. Für die Suche nach einem Eintrag muss die Eingabe natürlich mit dem gleichen Verfahren verarbeitet werden. Gibt man beispielsweise “gico” als Suche vor, so wird der Text umgewandelt in die Bigramme gi, ic und co. Nun werden alle Such-Bigramme im Index gesucht und einer Ergebnisliste hinzugefügt:
gi -> gigacode
ic -> nix
co -> gigacode
Anschließend kann man in der Ergebnismenge ein Scoring durchführen: Für jeden Treffer gibt es einen Pluspunkt. So erhält der Text “gigacode” 2 Punkte. Dies ist insbesondere wichtig, wenn wir z. B. nach “gaco” suchen:
ga -> gigacode, garage
ac -> gigacode
co -> gigacode
“gigacode” erhält hier die Score 3 während “garage” nur 1 erhält. Damit ist “gigacode” der “bessere” Treffer.
Implementierung #
Als Grundlage schaffe ich eine Vorverarbeitungskette für die Texte. Das Interface StringProcessor definiert eine Verarbeitungseinheit, welche einen String hineinbekommt und einen (eventuell anderen) String zurück gibt:
public interface StringProcessor {
String process(String inString);
}
Eine erste Verarbeitung der Eingabe ist die Erzeugung der Kleinschreibweise der Eingabe:
public class ToLowerCaseProcessor implements StringProcessor {
public String process(String inString) {
return inString.toLowerCase();
}
}
Eine weitere Verarbeitungseinheit entfernt alle Leerzeichen:
public class WhitespaceFilter implements StringProcessor {
public String process(String inString) {
char[] result = new char[inString.length()];
int resultIndex = 0;
for (int i = 0; i < inString.length(); i++) {
char c = inString.charAt(i);
if (!Character.isWhitespace(c)) {
result[resultIndex++] = c;
}
}
return new String(result, 0, resultIndex);
}
}
Es folgen Verarbeitungseinheiten für das Entfernen von nicht-Textzeichen (und nicht-Ziffern):
public class NonLetterNonDigitFilter implements StringProcessor {
public String process(String inString) {
char[] result = new char[inString.length()];
int resultIndex = 0;
for (int i = 0; i < inString.length(); i++) {
char c = inString.charAt(i);
if (Character.isLetter(c) || Character.isDigit(c)) {
result[resultIndex++] = c;
}
}
return new String(result, 0, resultIndex);
}
}
sowie eine Einheit, welche UTF-Sonderzeichen normalisiert, also aus z. B. ä ein ae macht.
public class DecomposeProcessor implements StringProcessor {
public String process(String inString) {
return Normalizer.normalize(inString, Normalizer.Form.NFD).replaceAll("\p{InCombiningDiacriticalMarks}+", "");
}
}
Zu guter Letzt gibt es eine Verarbeitungseinheit, die nichts macht und eine, die mehrere zusammenfasst:
public class NoOpStringProcessor implements StringProcessor {
public static final NoOpStringProcessor INSTANCE = new NoOpStringProcessor();
@Override
public String process(String input) {
return input;
}
public static final StringProcessor noOpIfNull(StringProcessor input) {
return input == null ? INSTANCE : input;
}
}
public class ChainedStringProcessor implements StringProcessor {
private final List<StringProcessor> delegateProcessors = new ArrayList<>();
public ChainedStringProcessor(Collection<StringProcessor> delegateProcessors) {
if (delegateProcessors != null) {
this.delegateProcessors.addAll(delegateProcessors);
}
}
public ChainedStringProcessor(StringProcessor... delegateProcessors) {
if (delegateProcessors != null) {
this.delegateProcessors.addAll(Arrays.asList(delegateProcessors));
}
}
@Override
public String process(String inputText) {
String processedInput = inputText;
for (StringProcessor stringProcessor : delegateProcessors) {
processedInput = stringProcessor.process(processedInput);
}
return processedInput;
}
}
Der Tokenizer übernimmt die Aufgabe Eingaben in Happen a N-Zeichen umzuwandeln:
public class NGramTokenizer implements Tokenizer {
private int n;
public NGramTokenizer(int n) {
this.n = n;
}
@Override
public List<String> tokenize(String inputText) {
List<String> nGrams = new ArrayList<>(Math.max(1 + (int) ((inputText.length() - (n - 1)) / 0.75), 0));
for (int i = 0; i < inputText.length() - (n - 1); i++) {
nGrams.add(inputText.substring(i, i + n));
}
return nGrams;
}
}
Das Dictionary (Wörterbuch) enthält Methoden zum Hinzufügen neuer Dokumente und zum Suchen vorhandener Dokumente:
public interface Dictionary {
Dictionary index(Text inputText);
List<Score> find(String searchInput);
}
Hierin finden sich die abstrahierten Texte:
public class Text {
private final String content;
private String processedContent;
public Text(String content) {
this.content = content;
}
public String getContent() {
return content;
}
public String getProcessedContent() {
return processedContent;
}
public void setProcessedContent(String processedContent) {
this.processedContent = processedContent;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o != null && o instanceof Text) {
Text text = (Text) o;
return getContent() != null ? getContent().equals(text.getContent()) : text.getContent() == null;
}
return false;
}
@Override
public int hashCode() {
return getContent() != null ? getContent().hashCode() : 0;
}
@Override
public String toString() {
return getContent();
}
}
und die Suchergebnisse:
public class Score {
private Text text;
private double score;
public Score() {
}
public Score(Text text, double score) {
this.text = text;
this.score = score;
}
public Text getText() {
return text;
}
public void setText(Text text) {
this.text = text;
}
public double getScore() {
return score;
}
public void setScore(double score) {
this.score = score;
}
public void incrementScore(double increment) {
setScore(getScore() + increment);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o != null && o instanceof Score) {
Score score = (Score) o;
return getText() != null ? getText().equals(score.getText()) : score.getText() == null;
}
return false;
}
@Override
public int hashCode() {
return getText() != null ? getText().hashCode() : 0;
}
@Override
public String toString() {
return "Score{" +
"text='" + text + '\\'' +
", score=" + score +
'}';
}
}
Die eigentliche Implementierung des Dictionary sieht dann wie folgt aus:
public class NGramDictionary implements Dictionary {
private int n;
private NGramTokenizer tokenizer;
// key: ngram
// value: all inputs (words) that contain the ngram
private Map<String, Set<Text>> textsByNGram = new HashMap<>();
public NGramDictionary(int n) {
if (n < 1) {
throw new IllegalArgumentException("n must be greater than 0");
}
this.n = n;
tokenizer = new NGramTokenizer(n);
}
@Override
public NGramDictionary index(final Text inputText) {
Set<String> inputNGrams = generateNGrams(inputText.getProcessedContent());
for (String inputNGram : inputNGrams) {
Set<Text> textsForNGram = textsByNGram.get(inputNGram);
if (textsForNGram == null) {
textsForNGram = new HashSet<>();
textsByNGram.put(inputNGram, textsForNGram);
}
textsForNGram.add(inputText);
}
return this;
}
@Override
public List<Score> find(final String searchInput) {
Set<String> inputNGrams = generateNGrams(searchInput);
Map<Text, Double> scoresByTexts = new HashMap<>(1 + (int) (inputNGrams.size() / 0.75));
for (String inputNGram : inputNGrams) {
Set<Text> textsForNGram = textsByNGram.get(inputNGram);
if (textsForNGram != null) {
for (Text textForNGram : textsForNGram) {
Double score = scoresByTexts.get(textForNGram);
if (score == null) {
score = 0D;
}
score = score + 1D;
scoresByTexts.put(textForNGram, score);
}
}
}
List<Score> scores = new ArrayList<>(1 + (int) (scoresByTexts.size() / 0.75));
for (Text text : scoresByTexts.keySet()) {
scores.add(new Score(text, scoresByTexts.get(text)));
}
return scores;
}
private Set<String> generateNGrams(String inputText) {
Set<String> inputNGrams = new HashSet<>(tokenizer.tokenize(inputText));
return inputNGrams;
}
@Override
public String toString() {
return "NGramDictionary[" + n + "]";
}
}