Thomas Darimont
Erfahrenes Mitglied
Just 4 Fun:
Ausgabe:
Java:
package de.tutorials;
import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
* @author Tom
*
*/
public class FuzzySearch {
/**
* @param args
*/
public static void main(String[] args) throws Exception {
Database db = new Database();
db.load("c:/temp/presidents.txt");
System.out.println(db.query("George Bush"));
System.out.println(db.query("JFK"));
System.out.println(db.query("oooo"));
}
static class Database {
List<String> index = new ArrayList<String>();
void load(String filePath) throws Exception {
Scanner scanner = new Scanner(new File(filePath));
while (scanner.hasNextLine()) {
index(scanner.nextLine());
}
scanner.close();
}
Iterable<String> query(String query) {
Map<String, List<MatchPart>> matches = new HashMap<String, List<MatchPart>>();
char[] queryChars = query.replace(" ","").toCharArray();
for (String item : index) {
char[] itemChars = item.toCharArray();
int itemIndex = 0;
int queryIndex = 0;
int alreadyMatchedQueryCharsCount = 0;
List<MatchPart> matchParts = new ArrayList<MatchPart>();
while (itemIndex < itemChars.length
&& queryIndex < queryChars.length) {
int currentQueryMatchStart = itemIndex;
boolean matched = false;
while (itemIndex < itemChars.length
&& queryIndex < queryChars.length
&& queryChars[queryIndex] == itemChars[itemIndex]) {
queryIndex++;
itemIndex++;
alreadyMatchedQueryCharsCount++;
matched = true;
}
if (matched) {
matchParts.add(new MatchPart(currentQueryMatchStart,
itemIndex + 1 // currentQueryMatchEnd
));
}
if (alreadyMatchedQueryCharsCount == queryChars.length) {
matches.put(item, matchParts); // Full match
break;
}
itemIndex++;
}
}
return renderMatches(matches);
}
Iterable<String> renderMatches(Map<String, List<MatchPart>> matches) {
List<String> renderedMatches = new ArrayList<String>();
for (String match : matches.keySet()) {
StringBuilder renderedMatch = new StringBuilder(match);
int extension = 0;
for (MatchPart matchPart : matches.get(match)) {
renderedMatch.insert(matchPart.start + extension, '<');
renderedMatch.insert(matchPart.end + extension, '>');
extension += 2;
}
renderedMatches.add(renderedMatch.toString());
}
return renderedMatches;
}
void index(String item) {
index.add(item);
}
static class MatchPart {
int start;
int end;
public MatchPart(int start, int end) {
this.start = start;
this.end = end;
}
}
}
}
Ausgabe:
Code:
[<George> H. <Bush>, <George> W. <Bush>]
[<J>ohn <F>. <K>ennedy]
[W<oo>dr<o>w Wils<o>n, The<o>d<o>re R<oo>sevelt]