Wydajne algorytmy przeszukiwania kolekcji drzew

9

Mam duży zestaw danych o drzewach i chciałbym je przeszukać, określając treelet (połączony podgrupa). Kwerenda powinna zwrócić wszystkie wystąpienia treeline w zbiorze danych.

Czy istnieją wydajne algorytmy do tego celu?

Myślałem o czymś takim jak tablice sufiksów, jednak naiwne kodowanie drzew, ponieważ łańcuchy (przez ustaloną kolejność ich węzłów) nie będą działać, ponieważ szkielet wyszukiwania może mieć dowolny dowolny kształt.

AKTUALIZACJA:

Kilka szczegółów na temat typowych przypadków, których oczekuję:

Zbiór danych będzie się składał z co najmniej dziesiątek tysięcy drzew, z których każde składa się z około dwudziestu do trzydziestu węzłów. Drzewa nie będą binarne, ale typowa liczba dzieci na węzeł będzie niewielka (zwykle nie większa niż cztery lub pięć, chociaż w niektórych zdegenerowanych przypadkach może osiągnąć około trzydziestu). Liczba etykiet wyniesie dziesiątki tysięcy.

Potrzebuję tego dla aplikacji NLP: każde drzewo będzie parsowaniem zależności zdania, każdy węzeł reprezentuje występowanie słowa, a każda etykieta słowo słownikowe (z pewną dekoracją).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Antonio Valerio Miceli-Barone
źródło
1
Ten tom zawiera omówienie równoległych algorytmów dla izomorfizmu poddrzewa.
Anthony Labarre
1
Przepraszam, myślałem, że szukałeś połączonego podsgrafu, który koniecznie będzie drzewem, pojawiającym się w danym zbiorze drzew. Czy możesz wyjaśnić, w jakich aspektach twój problem różni się od tego opisu?
Anthony Labarre
1
Czy wiesz coś o drzewach z góry? Dwójkowy? Jak wielu różnych etykiet węzłów oczekujesz? Jakieś ograniczenia dotyczące wydajności przestrzeni? Pytam, ponieważ jeśli prowadzisz masę zapytań w tym samym zestawie danych, rozwiązanie może wymagać pewnego rodzaju agresywnego indeksowania.
Eli
1
Czy znasz dopasowanie XML gałązek? Twój problem wydaje się być szczególnym przypadkiem, więc możesz po prostu użyć dowolnego z istniejących algorytmów i oprogramowania.
Marek Chrobak
2
Myślę, że najlepiej zignorować strukturę wykresu. Biorąc pod uwagę typowe pytanie, jeśli odrzucisz strukturę, ile drzew spodziewasz się wszystkich tych słów? Czy twoje zapytania zawierają jakieś symbole wieloznaczne, czy są dokładne? Jeśli słowa w zapytaniu są podobne do „Kot zjadł kapelusz”, to ile wykresów będzie zawierało zarówno słowa „kot”, jak i „kapelusz”? Jeśli po prostu indeksujesz każde słowo do zestawu drzew, a następnie przecinasz wszystkie zestawy, potencjalnie możesz naiwnie przeszukać wynik bez ponoszenia zbyt dużych kosztów.
Eli

Odpowiedzi:

3

Chociaż nie jest specjalnie ukierunkowany na (ukorzenione) drzewa, myślę, że struktura danych G-trie może działać całkiem dobrze w twoim otoczeniu. Jest to adaptacja trie (do wyszukiwania zestawów ciągów) do wykresów.

Joshua Grochow
źródło
1

Jakiś czas temu napisałem algorytm kanonizacji drzew Ronalda Reada i umieściłem go na wikipedii .

Zrobiłbym hashtable dla każdego podpisu wewnętrznego węzła i oznaczyłbym je listą wskaźników z powrotem do poddrzewa, z którego pochodzą. Będzie to jednak działać tylko w przypadku treeline z prawdziwymi liśćmi.

Chad Brewbaker
źródło