algorithm

사람들이이 질문을 발견하고 Node.js 또는 브라우저에 대해 구현 된 것이 필요한 경우 여기에 github에서 찾을 수있는 구현에 대한 링크와 코드 예제를 제공하고 있습니다. https://github.com /hoonto/jqgram.git ) 기존 PyGram Python 코드 ( https://github.com/Sycondaman/PyGram )를 기반으로합니다 .

이것은 트리 편집 거리 근사치입니다. 알고리즘이지만 실제 편집 거리를 찾는 것보다 훨씬 빠릅니다. 근사는 O (n log n) 시간 및 O (n) 공간에서 수행되는 반면 실제 편집 거리는 실제 편집 거리에 대해 알려진 알고리즘을 사용하여 종종 O (n ^ 3) 또는 O (n ^ 2)입니다. PQ-Gram 알고리즘이 제공되는 학술 논문을 참조하십시오 : ( http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf )

따라서 jqgram 사용 :

예:

var jq = require("jqgram").jqgram;
var root1 = {
    "thelabel": "a",
    "thekids": [
        { "thelabel": "b",
        "thekids": [
            { "thelabel": "c" },
            { "thelabel": "d" }
        ]},
        { "thelabel": "e" },
        { "thelabel": "f" }
    ]
}

var root2 = {
    "name": "a",
    "kiddos": [
        { "name": "b",
        "kiddos": [
            { "name": "c" },
            { "name": "d" },
            { "name": "y" }
        ]},
        { "name": "e" },
        { "name": "x" }
    ]
}

jq.distance({
    root: root1,
    lfn: function(node){ return node.thelabel; },
    cfn: function(node){ return node.thekids; }
},{
    root: root2,
    lfn: function(node){ return node.name; },
    cfn: function(node){ return node.kiddos; }
},{ p:2, q:3 },
function(result) {
    console.log(result.distance);
});

그리고 그것은 당신에게 0과 1 사이의 숫자를 제공합니다. 0에 가까울수록 두 나무가 jqgram을 더 가깝게 보입니다. 한 가지 접근 방식은 jqgram을 사용하여 속도가 주어진 여러 트리 중에서 밀접하게 관련된 여러 트리를 좁힌 다음 면밀한 검사가 필요한 나머지 몇 개의 트리에 대한 실제 편집 거리를 활용하여 파이썬을 찾을 수 있습니다. 예를 들어 Zhang & Shasha 알고리즘의 참조 또는 포트에 대한 구현.

lfn 및 cfn 매개 변수는 각 트리가 각 트리 루트에 대한 노드 레이블 이름과 자식 배열을 독립적으로 결정하는 방법을 지정하여 예를 들어 개체를 브라우저 DOM과 비교하는 것과 같은 펑키 한 작업을 수행 할 수 있습니다. 각 루트와 함께 해당 함수를 제공하기 만하면 jqgram이 나머지를 수행하여 lfn 및 cfn 제공 함수를 호출하여 트리를 구축합니다. 따라서 그런 의미에서 PyGram보다 사용하기가 훨씬 쉽습니다. 또한 Javascript이므로 클라이언트 또는 서버 측을 사용하십시오!

또한주기 감지와 관련하여 대답하려면 jqgram 내부의 복제 방법을 확인하십시오. 거기에주기 감지가 있지만 그 부분이 약간 수정되고 포함 된 node-clone의 작성자에게 있습니다.