1. 교통 분류: 편집 거리 (Levenshtein 거리) 자바 실현
집합 을 통 해 차량 노선 의 규칙 적 분석 을 실현 하려 면 먼저 싱크로 율 문 제 를 해결 해 야 한다. 우 리 는 싱크로 율 을 계산 할 때 공간 벡터 거리 (유럽식 거리, 코사인 싱크로 율) 등 알고리즘 을 사용 할 수 있다 는 것 을 알 고 있다.그러나 이런 요구 에 적응 하지 못 하기 때문에 편집 거리 로 이 문 제 를 해결 해 야 한다.
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
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.