1. 교통 분류: 편집 거리 (Levenshtein 거리) 자바 실현

1. 최근 작업 중 에 사용자 차량 의 운행 노선 의 집합 을 실현 해 야 합 니 다. 주어진 데 이 터 는 사용자 가 하루 동안 교통 카드 가 감시 하 는 카드 이름 만 있 기 때 문 입 니 다. 즉, 칭 다 오 로 - 웨 이하 이 로 - 제 양 로 입 니 다.
집합 을 통 해 차량 노선 의 규칙 적 분석 을 실현 하려 면 먼저 싱크로 율 문 제 를 해결 해 야 한다. 우 리 는 싱크로 율 을 계산 할 때 공간 벡터 거리 (유럽식 거리, 코사인 싱크로 율) 등 알고리즘 을 사용 할 수 있다 는 것 을 알 고 있다.그러나 이런 요구 에 적응 하지 못 하기 때문에 편집 거리 로 이 문 제 를 해결 해 야 한다.
 
2. 거리의 사상 편집:
a. 두 문자열 사이 에 한 문자열 에서 다른 문자열 로 전환 하 는 데 필요 한 최소 편집 작업 횟수 를 말 합 니 다.허 가 된 편집 작업 은 한 문 자 를 다른 문자 로 바 꾸 고 한 문 자 를 삽입 하여 한 문 자 를 삭제 하 는 것 을 포함한다.
예 를 들 어 kitten 을 sitting 으로 전환 합 니 다.
1.sitten (k->s)
2.sittin (e –> i)
3.sitting (-> g)
러시아 과학자 Vladimir Levenshtein 이 1965 년 에 제기 한 이 개념
3. 문제: 문자열 의 편집 거 리 를 찾 습 니 다. 즉, 하나의 문자열 S1 을 최소 몇 단계 의 작업 을 거 쳐 문자열 S2 로 바 꾸 는 것 입 니 다. 작업 은 세 가지 가 있 습 니 다. 문 자 를 추가 하고 문 자 를 삭제 하 며 문 자 를 수정 합 니 다.
해석: 먼저 이러한 함수 - edit (i, j) 를 정의 합 니 다. 첫 번 째 문자열 의 길 이 는 i 의 하위 문자열 에서 두 번 째 문자열 의 길 이 는 j 의 하위 문자열 의 편집 거 리 를 표시 합 니 다.
분명히 다음 과 같은 동적 기획 공식 이 있다.
1. if i = = 0 및 j = = 0, edit (i, j) = = 0
2. if  i = = 0 및 j > 0, edit (i, j) = = j
3. if i > 0 및 j = = 0, edit (i, j) = = i
4. if i > = 1 및 j > = 1, edit (i, j) = = min {edit (i - 1, j) + 1, edit (i, j - 1) + 1, edit (i – 1, j - 1) + f (i, j)} 첫 번 째 문자열 의 i 문자 가 두 번 째 문자열 의 j 문자 와 같 지 않 을 때 f (i, j) = 1;그렇지 않 으 면 f (i, j) = 0.
 
4. 상위 코드:

package com.dk.route;

/**
 *     ,        
 * @author zzy
 *
 */
public class LevenshteinDistance {
    public static void main (String[] args){
        
        String str1 = "                                                  ";
        String str2 = "               S217   -                ";
        
//        String str2 = "S217   -     ";//S217   -     
//        String str1 = "    （  -   ）K23+800      ";
//        String str2 = "   ";
//        String str1 = "  ";
        System.out.println("ld= "+ levenshteinDistance(str1, str2));
//        System.out.println("sim="+sim(str1,str2) );
    }
    private static int min(int one,int two,int three){
        int min = one;
        if (two < min){
            min = two;
        }
        if (three <min){
            min = three;
        }
        return min;
    }
    public static int levenshteinDistance(String str1,String str2){
        
        int d[][]; //   
        int n = str1.length();
        int m = str2.length();
        int i ; // for str1
        int j; // for str2
        char ch1;
        char ch2;
        int temp; //       ,           ,  0  1;
        if(n == 0){
            return m;
        }
        if (m == 0){
            return n;
        }
        d = new int [n+1][m+1];
        for ( i = 0; i < n ; i++) { //       
            d[i][0] = i; 
        }
        for(j = 0; j<= m;j++){ //       
            d[0][j] = j;
        }
         for (i =1; i<= n;i++){
             ch1 = str1.charAt(i-1);
             for(j=1;j <= m;j++){
                 ch2 = str2.charAt(j-1);
                 if(ch1 == ch2){
                     temp = 0;
                 }else{
                     temp =1;
                 }
                 d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+temp);
             }
         }
         return d[n][m];
        
        
    }
    public static double sim (Route initR,Route r){

        if (initR.routename == null || r.routename == null){
            return 0;
        }
        String str1 = initR.routename;
        String str2 = r.routename;
        double ld = levenshteinDistance(str1, str2);
        double strMax = Math.max(str1.length(), str2.length());
        double sim =1- ld/strMax;
//        if(ld < strMax){
//            sim = 1-ld/Math.min(str1.length(), str2.length());
//        }

//        System.out.println(initR.routename +"------- -------" +r.routename +"    =" + sim);
        return sim;
    }
    
}

 
원본 코드:https://github.com/chaoren399/dkdemo/blob/master/agenes/src/agenesdemo/LevenshteinDistance.java