PHP 싱크로 율 계산 함수:levenshtein 사용 설명

사용 설명 은 매 뉴 얼 에 있 는 levenshtein()함수 의 설명 을 먼저 보십시오.
levenshtein()함수 가 두 문자열 사이 의 Levenshtein 거 리 를 되 돌려 줍 니 다.
Levenshtein 거 리 는 편집 거리 라 고도 부 르 는데 두 문자열 사이 에 하나 에서 다른 것 으로 전환 하 는 데 필요 한 최소 편집 작업 횟수 를 말한다.허 가 된 편집 작업 은 한 문 자 를 다른 문자 로 바 꾸 고 한 문 자 를 삽입 하여 한 문 자 를 삭제 하 는 것 을 포함한다.
예 를 들 어 kitten 을 sitting 으로 변환 합 니 다.
sitten(k→s)sittin(e→i)sitting(→g)levenshtein()함 수 는 모든 조작(교체,삽입,삭제)과 같은 가중치 입 니 다.단,선택 한 insert,replace,delete 인 자 를 설정 하여 모든 작업 의 대 가 를 정의 할 수 있 습 니 다.
문법:
levenshtein(string1,string2,insert,replace,delete)
매개 변수 설명
string 1 필수.비교 할 첫 번 째 문자열 입 니 다.string 2 필수.비교 할 두 번 째 문자열 입 니 다.insert 선택 가능.문자 삽입 대가.기본 값 은 1.replace 선택 가능.문자 교체 의 대가.기본 값 은 1.delete 선택 가능.문자 하 나 를 삭제 하 는 대가.기본 값 은 1.제시 와 주석
한 문자열 이 255 자 를 넘 으 면 levenshtein()함수 가-1 을 되 돌려 줍 니 다.levenshtein()함 수 는 대소 문자 에 민감 하지 않 습 니 다.levenshtein()함수 비 similartext()함수 가 더 빠 릅 니 다.하지만,similartext()함 수 는 더 적은 수정 이 필요 한 더 정확 한 결 과 를 제공 합 니 다.예

<?php
    echo levenshtein("Hello World","ello World");
    echo "<br />";
    echo levenshtein("Hello World","ello World",10,20,30);
    ?>

출력:130
원본 분석 levenshtein()은 표준 함수 에 속 합 니 다./ext/standard/디 렉 터 리 에 이 함수 에 대한 파일 이 있 습 니 다:levenshtein.c.
levenshtein()은 매개 변수 개수 에 따라 실현 방식 을 선택 하고 매개 변수 가 2 와 매개 변수 가 5 인 경우 reference 를 호출 합 니 다.levdist()함수 계산 거리.그 차이 점 은 뒤의 세 개의 매개 변수,매개 변수 가 2 일 때 기본 값 1 을 사용 하 는 것 이다.
또한 소스 코드 를 실현 하 는 과정 에서 우 리 는 문서 에 설명 되 지 않 은 상황 을 발견 했다.levenshtein()함 수 는 세 개의 인 자 를 전달 할 수 있 고 최종 적 으로 custom 을 호출 할 것 이다.levdist()함수.이 는 세 번 째 매개 변 수 를 사용자 정의 함수 로 실현 합 니 다.호출 예 는 다음 과 같 습 니 다.

echo levenshtein("Hello World","ello World", 'strsub');

실행 회 는 Warning:The genel Levenshtein support is not there yet.이것 은 현재 이 방법 이 아직 실현 되 지 않 았 기 때문에 단지 구 덩이 를 거기에 두 었 을 뿐이다.
reference_levdist()함수 의 구현 알고리즘 은 전형 적 인 DP 문제 입 니 다.
두 문자열 x 와 y 를 지정 하고 최소한 의 수정 횟수 를 구하 면 x 를 y 로 바 꿉 니 다.수 정 된 규칙 은 다음 과 같은 세 가지 중 하나 일 수 있 습 니 다.삭제,삽입,변경.a[i][j]로 x 의 앞 i 문 자 를 y 의 앞 j 문자 로 바 꾸 는 데 필요 한 최소 조작 횟수 를 표시 하면 상태 전이 방정식 은

 x[i]==y[j] ：a[i][j]  = min(a[i-1][j-1], a[i-1][j]+1, a[i][j-1]+1);
 x[i]!=y[j] ：a[i][j] =  min(a[i-1][j-1], a[i-1][j], a[i][j-1])+1;

상태 전이 방정식 을 사용 하기 전에(n+1)(m+1)의 행렬 d 를 초기 화하 고 첫 줄 과 열의 값 을 0 부터 증가 시 켜 야 한다.두 문자열(nm 급)을 스 캔 하고 문 자 를 비교 하 며 상태 이동 방정식 을 사용 합 니 다.최종$a[$l1][$l2]는 그 결과 입 니 다.
간단 한 실현 과정 은 다음 과 같다.

<?PHP
    $s1 = "abcdd";
    $l1 = strlen($s1);
    $s2 = "aabbd";
    $l2 = strlen($s2);

 
    for ($i = 0; $i < $l1; $i++) {
        $a[0][$i + 1] = $i + 1;
    }
    for ($i = 0; $i < $l2; $i++) {
        $a[$i + 1][0] = $i + 1;
    }

    for ($i = 0; $i < $l2; $i++) {
        for ($j = 0; $j < $l1; $j++) {
            if ($s2[$i] == $s1[$j]) {
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1] + 1, $a[$i + 1][$j] + 1);
            }else{
                $a[$i + 1][$j + 1] = min($a[$i][$j], $a[$i][$j + 1], $a[$i + 1][$j]) + 1;
            }
        }
    }

    echo $a[$l1][$l2];
    echo "n";
    echo levenshtein($s1, $s2);

PHP 의 실현 에서 실현 자 는 주석 에 명확 하 게 표시 되 어 있다.이 함 수 는 메모리 사용 만 최적화 하고 속 도 를 고려 하지 않 았 다.그 실현 알고리즘 을 보면 시간 복잡 도 는 O(m)이다.×n)。그 최적화 점 은 위의 상태 전이 방정식 중의 2 차원 배열 을 두 개의 배열 로 바 꾸 는 데 있다.간단하게 다음 과 같이 실현 합 니 다.

<?PHP
    $s1 = "abcjfdkslfdd";
    $l1 = strlen($s1);
    $s2 = "aab84093840932bd";
    $l2 = strlen($s2);

    $dis = 0;
    for ($i = 0; $i <= $l2; $i++){
        $p1[$i] = $i;
    }

    for ($i = 0; $i < $l1; $i++){
        $p2[0] = $p1[0] + 1;

        for ($j = 0; $j < $l2; $j++){
            if ($s1[$i] == $s2[$j]){
                $dis = min($p1[$j], $p1[$j + 1] + 1, $p2[$j] + 1);
            }else{
                $dis = min($p1[$j] + 1, $p1[$j + 1] + 1, $p2[$j] + 1);  //            $p2  
            }
            $p2[$j + 1] = $dis;
        }
        $tmp = $p1;
        $p1 = $p2;
        $p2 = $tmp;  
    }

    echo "n";
    echo $p1[$l2];
    echo "n";
    echo levenshtein($s1, $s2);

예 를 들 어 PHP 커 널 개발 자 들 이 앞의 전형 적 인 DP 에 대한 최적화 점 은 두 개의 1 차원 배열 을 계속 재 활용 하 는 것 입 니 다.하 나 는 지난번 결 과 를 기록 하고 하 나 는 이번 결 과 를 기록 하 는 것 입 니 다.PHP 의 매개 변수 에 따라 세 개의 조작 할당 값 이 다 르 면 위의 알고리즘 에서 대응 하 는 1 을 조작 에 대응 하 는 값 으로 바 꾸 면 됩 니 다.min 함수 의 첫 번 째 매개 변 수 는 수정 에 대응 하고 두 번 째 매개 변 수 는 원본 하늘 을 삭제 하 는 것 이 며 세 번 째 매개 변 수 는 추가 에 대응 합 니 다.
Levenshtein distance 는 Levenshtein distance 가 가장 먼저 러시아 과학자 Vladimir Levenshtein 이 1965 년 에 발명 하여 그의 이름 으로 명명 되 었 다 는 것 을 설명 한다.맞 춤 법 을 읽 을 줄 모 르 고 edit distance(편집 거리)라 고 부 를 수 있 습 니 다.Levenshtein distance:Spell checking(맞 춤 법 검사)Speech recognition(구문 인식)DNA analysis(DNA 분석)Plagiarism detection(표절 검사)LD 는 mn 의 매트릭스 로 거리 값 을 저장 할 수 있 습 니 다.