Ocena jakości dopasowań sznurkowych
Jaki byłby najlepszy sposób, aby porównać wzór z zestawem ciągów, jeden po drugim, podczas gdy oceniając ilość, z jaką wzór pasuje do każdego ciągu? W moim ograniczonym doświadczeniu z regex, dopasowanie ciągów z wzorcami za pomocą regex wydaje się być dość binarne operation...no nieważne, jak skomplikowany jest wzór, w końcu albo pasuje, albo nie. szukam większych możliwości, poza samym dopasowaniem. Czy istnieje dobra technika lub algorytm, który odnosi się do to?
Oto przykład:
Powiedzmy, że mam wzór foo bar
i chcę znaleźć ciąg, który najbardziej pasuje do niego z następujących ciągów:
foo for
foo bax
foo buo
fxx bar
Żaden z nich nie pasuje do wzorca, ale który z nich jest najbliższy do dopasowania? W tym przypadku foo bax
byłby najlepszym wyborem, ponieważ pasuje do 6 z 7 znaków.
Przepraszam, jeśli to jest duplikat pytania, naprawdę Nie wiem, co dokładnie szukać kiedy spojrzałem, aby zobaczyć, czy to pytanie już istnieje.
2 answers
Ten działa, sprawdziłem na przykładzie Wikipedii distance between "kitten" and "sitting" is 3
public class LevenshteinDistance {
public static final String TEST_STRING = "foo bar";
public static void main(String ...args){
LevenshteinDistance test = new LevenshteinDistance();
List<String> testList = new ArrayList<String>();
testList.add("foo for");
testList.add("foo bax");
testList.add("foo buo");
testList.add("fxx bar");
for (String string : testList) {
System.out.println("Levenshtein Distance for " + string + " is " + test.getLevenshteinDistance(TEST_STRING, string));
}
}
public int getLevenshteinDistance (String s, String t) {
if (s == null || t == null) {
throw new IllegalArgumentException("Strings must not be null");
}
int n = s.length(); // length of s
int m = t.length(); // length of t
if (n == 0) {
return m;
} else if (m == 0) {
return n;
}
int p[] = new int[n+1]; //'previous' cost array, horizontally
int d[] = new int[n+1]; // cost array, horizontally
int _d[]; //placeholder to assist in swapping p and d
// indexes into strings s and t
int i; // iterates through s
int j; // iterates through t
char t_j; // jth character of t
int cost; // cost
for (i = 0; i<=n; i++) {
p[i] = i;
}
for (j = 1; j<=m; j++) {
t_j = t.charAt(j-1);
d[0] = j;
for (i=1; i<=n; i++) {
cost = s.charAt(i-1)==t_j ? 0 : 1;
// minimum of cell to the left+1, to the top+1, diagonally left and up +cost
d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
}
// copy current distance counts to 'previous row' distance counts
_d = p;
p = d;
d = _d;
}
// our last action in the above loop was to switch d and p, so p now
// actually has the most recent cost counts
return p[n];
}
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-11-05 17:05:03
Ciekawe pytanie! Pierwszą rzeczą, która przyszła na myśl jest to, że sposób dopasowania wyrażeń regularnych jest budowaniem DFA . Jeśli masz bezpośredni dostęp do DFA, który został zbudowany dla danego regex (lub po prostu zbudował go sam!) możesz uruchomić pomiar wejściowy odległości od ostatniego stanu, do którego się przeszedłeś i stanu accept, używając najkrótszej ścieżki jako miary tego, jak blisko było zaakceptowania, ale nie jestem świadomy żadnych bibliotek, które pozwoliłyby ci to zrobić że łatwo i nawet ten środek prawdopodobnie nie dokładnie odwzorować na intuicji w wielu przypadkach.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-11-05 15:23:23