트리 매칭 알고리즘?

Question

tree 라이브러리에서 작업 중이며 필요한 기능 중 일부는 패턴과 일치하는 하위 노드를 노드에서 검색 할 수 있습니다.

'패턴'은 일치시킬 하위 트리의 노드 속성뿐만 아니라 구조를 레이아웃하는 사양 (또는 기준)입니다.

예를 들어 트리가 특정 종의 새에 관한 데이터를 나타냅니다. 또한 이러한 트리의 노드가 다음과 같은 속성이 있다고 가정 :

• 위치를
• 섹스
• 날개
• 부모 노드 감안할 때 brood_size는

, 내가 것 체중

평범한 영어로 검색하기를 좋아합니다 :

"이 새의 후손 인 의 모든 수컷 새들을 데려와 XXX 도시에 거주하고 체중> 100g. 발견 그러한 조류해야 또한 적어도 두 형제와 한 자매가 있고, 그 자체가 하나 이상의 아이를 "이 있어야합니다

< 노트>

그냥 내가 수 있기를 기대하지 않는다, 명확하게 위에서 수행 한 것처럼 일반 영어를 사용하여 쿼리 할 수 ​​있습니다. 트리에서 수행하려는 일치 유형을 설명하기 위해 "일반 영어 쿼리"만 사용했습니다. 일치를 위해 기호를 사용할 것으로 완전히 기대합니다 (일반 텍스트).

</note>

아마도 나무와 일치하는 정규식 형식 패턴을 사용하려고 생각하고 있습니다. 한 가지 방법은 각 정규 표현식을 사용할 수 있도록 각 노드의 문자열 표현을 사용하는 것입니다. 그러나 반복되는 데이터가 많아 지므로 매우 비효율적 일 수 있습니다. 즉 하위 노드의 문자열 표현은 그들의 부모 표현은 그들의 부모 표현 문자열의 상위 집합이 될 것입니다. 재귀 적으로 나무 위로 - 이것은 적당한 크기의 나무에 대해 다루기가 쉽지 않을 수 있습니다 - 더 좋은 방법이 있어야합니다.

패턴을 기반으로 노드에서 노드 (하위 트리)를 선택할 수있는 알고리즘을 알고있는 사람이 있습니까?

일반적인 알고리즘을 요청했지만 파이썬에서 구현하고 있습니다. 그러한 알고리즘 (실제로 쓰여질 수있는 경우)을 자세히 보여주는 조각은 엄청나게 유용 할 것입니다.

Answer 1

이것은 트리에 따라 다릅니다. 트리가 루팅되고 주문 된 경우 하위 선형 시간으로 정확하게 일치하는지 확인할 수 있어야하며 그렇지 않은 경우 선형 시간으로 일치하는지 확인할 수 있어야합니다. 근사 일치를위한 몇 가지 빠른 알고리즘도 있습니다.

이와 비슷한 주제의 알고리즘과 알고리즘을 찾으려면 Google Scholar이 (가) 친구입니다. 하위 트리 일치 검색 또는 유사 검색이 가능합니다.

EDIT : 업데이트 된 항목으로 판단 할 때 XPath 및 유사한 쿼리 언어가 어떻게 구현되는지 살펴 보시기 바랍니다. XML은 루트 트리이며, XPath는 예제에서와 같이 복잡한 일치 연산자를 사용하여 해당 트리의 하위 트리를 검색 할 수 있습니다.

또한 직접 구현하지 말고 기존 라이브러리 (예 : PyLucene 또는 다른 검색 엔진과 같이 사용하는 것이 좋습니다)를 사용하는 것이 좋습니다.

Answer 2

트리 일치를 설명하기 위해 와일드 카드로 Lisp Sexpression을 쓰는 것이 잘못된 이유는 무엇입니까? 괄호는 노드를 그룹화합니다. 왼쪽에서 오른쪽으로 요소가 루트에 이어 아이가옵니다. 하위 트리 일치는 중첩 된 Sexpressions을 사용하여 하위 트리를 설명합니다.

임의 루트 노드와 나무를 일치합니다 다음, 첫 아이가 X와 뿌리 하위 트리, 첫 아이 하나와 세 번째 아이 A를 인 리프 A, 셋째 아이 인 :

(?root A ? (X 1 A)) 

이 아이디어 ISN ' 나에게 유일한 t; Lisp 사람들은 60 년대 초반부터 그런 패턴을 쓰고있다. 이 http://norvig.com/paip/patmatch.lisp

그러나,이 코딩하는 것은 자신이 매우 간단합니다 :

여기에만 다시 이십년 간다 (당신이 원하는 예를 들어 같은) LISP 패턴 매처입니다. 이것은 일반적으로 LISP를 배우는 사람들을위한 숙제로 할당됩니다.