Substitution tree


Substitution tree w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Substitution tree – metoda indeksowania termów polegająca na trzymaniu w każdym termie podstawienia, które należy wykonać na węźle rodzicu żeby uzyskać dany term.

W substitution tree inaczej traktowane są zmienne zewnętrzne (czyli po prostu pewne symbole) oraz zmienne wewnętrzne (służące wyłącznie do opisywania części wspólnych drzew).

Przykład dla g ( b ) , {\displaystyle g(b),} f ( a , g ( b ) ) {\displaystyle f(a,g(b))} i f ( b , g ( b ) ) : {\displaystyle f(b,g(b)){:}}

x {\displaystyle x} i y {\displaystyle y} są tu zmiennymi wewnętrznymi.

W substitution tree ma miejsce o wiele więcej współdzielenia niż w drzewie dyskryminacyjnym, jest więc ono pamięciowo o wiele bardziej wydajne. Wciąż jednak g ( b ) {\displaystyle g(b)} jest dzielone jedynie pomiędzy niektórymi wystąpieniami.

Na podstawie artykułu: "Substitution tree" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy