同じ都市のスペルが間違っている都市のリストがあります。1 つの都市のスペルが 18 回も間違っています。これをクリーンアップしようとしていますが、何時間もかかります。これらのスペルミスのある都市名の有効な都市名を「推測」するアルゴリズムはありますか? ある種の加重？データはMySQLにあり、比較するための正しいスペルの表もあります.
これに関するアイデアはありますか？可能であれば、PHP の例が役立ちます。
4582 次
3 に答える
4
damerau-levenstein 関数を使用して、2 つのストリング間のストリング距離を取得できます。（これは転置もチェックします）
http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
テーブルが大きい場合、文字列の距離がしきい値を超えたら、アルゴを少し最適化してブレークする必要があるかもしれません。
また、都市の最初の文字が正しく入力されていると仮定できる場合は、比較の数を減らす必要があります。
それはPHPではありませんが、もし何か助けがあれば、私が書いたJavaバージョンがここにあります:
class LevinshteinDistance{
public static void main(String args[]){
if(args.length != 2){
System.out.println("Displays the Levenshtein distance between 2 strings");
System.out.println("Usage: LevenshteinDistance stringA stringB");
}else{
int distance = getLevenshteinDistance(args[0], args[1]);
System.out.print(getLevenshteinMatrix(args[0], args[1]));
System.out.println("Distance: "+distance);
}
}
/**
* @param a first string for comparison
* @param b second string for comparison
* @param caseSensitive whether or not to use case sensitive matching
* @return a levenshtein string distance
*/
public static int getLevenshteinDistance(String a, String b, boolean caseSensitive){
if(! caseSensitive){
a = a.toUpperCase();
b = b.toUpperCase();
}
int[][] matrix = generateLevenshteinMatrix(a, b);
return matrix[a.length()][b.length()];
}
/**
* @param a first string for comparison
* @param b second string for comparison
* @return a case sensitive levenshtein string distance
*/
public static int getLevenshteinDistance(String a, String b){
int[][] matrix = generateLevenshteinMatrix(a, b);
return matrix[a.length()][b.length()];
}
/**
* @param a first string for comparison
* @param b second string for comparison
* @return a case sensitive string representation of the search matrix
*/
public static String getLevenshteinMatrix(String a, String b){
int[][] matrix = generateLevenshteinMatrix(a, b);
StringBuilder result = new StringBuilder();
final int ROWS = a.length()+1;
final int COLS = b.length()+1;
result.append(rowSeperator(COLS-1, false));
result.append("| "+b+" |\n");
result.append(rowSeperator(COLS-1, true));
for(int r=0; r<ROWS; r++){
result.append('|');
if(r > 0){
result.append(a.charAt(r-1));
}else{
result.append(' ');
}
result.append(" |");
for(int c=0; c<COLS; c++){
result.append(matrix[r][c]);
}
result.append(" |\n");
}
result.append(rowSeperator(COLS-1, false));
return result.toString();
}
private static String rowSeperator(final int LEN, boolean hasGap){
StringBuilder result = new StringBuilder();
if(hasGap){
result.append("+ +-");
}else{
result.append("+----");
}
for(int i=0; i<LEN; i++)
result.append('-');
result.append("-+\n");
return result.toString();
}
private static int[][] generateLevenshteinMatrix(String a, String b){
final int ROWS = a.length()+1;
final int COLS = b.length()+1;
int matrix[][] = new int[ROWS][COLS];
for(int r=0; r<ROWS; r++){
matrix[r][0]=r;
}
for(int c=0; c<COLS; c++){
matrix[0][c]=c;
}
for(int r=1; r<ROWS; r++){
char cA = a.charAt(r-1);
for(int c=1; c<COLS; c++){
char cB = b.charAt(c-1);
int cost = (cA == cB)?0:1;
int deletion = matrix[r-1][c]+1;
int insertion = matrix[r][c-1]+1;
int substitution = matrix[r-1][c-1]+cost;
int minimum = Math.min(Math.min(deletion, insertion), substitution);
if( (r > 1 && c > 1) && a.charAt(r-2) == cB && cA == b.charAt(c-2) ){
int transposition = matrix[r-2][c-2]+cost;
minimum = Math.min(minimum, transposition);
}
matrix[r][c] = minimum;
}
}
return matrix;
}
}
于 2010-08-18T18:19:16.157 に答える
2
レーベンシュタイン距離について読む: http://en.wikipedia.org/wiki/Levenshtein_distance .
実装を見つけるか、独自のものを作成してください。それほど複雑ではありません。
ニアミスのスペルミスを見つけるために使用します。
于 2010-08-18T18:16:38.780 に答える
1
悪名高い「Bariteney Spears」が示唆するように、そしてほとんどの人が経験から知っているように、Google はクローリングを通じて、人気のある名前の正確なスペル チェックをかなり得意としてきました。市は通常、よく修正するものです。したがって、Google 検索ページを解析して Google が提案する修正を確認する PHP 関数を作成しようとするかもしれませんし、さらに複雑な場合 (ページがより複雑なため)、Google マップによって提供されたオプションを解析しようとすることさえあるかもしれません。
于 2010-08-19T01:45:52.030 に答える