Como você armazenar um trie em um banco de dados relacional?

votos
11

Eu tenho um trie prefixo. Qual é o esquema recomendado para representar essa estrutura em um banco de dados relacional? Eu preciso substring correspondente a permanecer eficiente.

Publicado 10/12/2008 em 05:06
fonte usuário
Em outras línguas...                            


2 respostas

votos
6

Como sobre o caminho materializado design?

CREATE TABLE trie (
  path VARCHAR(<maxdepth>) PRIMARY KEY,
  ...other attributes of a tree node...
);

Para armazenar uma palavra como "stackoverflow":

INSERT IGNORE  INTO trie (path) VALUES
  ('s'), ('st'), ('sta'), ('stac'), ('stack'),
  ('stacko'), ('stackov'), ('stackove'), ('stackover'),
  ('stackover'), ('stackoverf'), ('stackoverflo'),
  ('stackoverflow');

O caminho materializado na árvore é a sequência de pré-fixada de si caracteres. Isso também constitui a chave primária. O tamanho da coluna varchar é a profundidade máxima de trie você deseja armazenar.

Eu não posso pensar em nada mais simples e direta do que isso, e preserva o armazenamento corda eficiente e pesquisa.

Respondeu 10/12/2008 em 05:15
fonte usuário

votos
0

Será que qualquer um dos seus entidades têm um relacionamento com qualquer outro? Se não, isto é, não relacional, uma tabela hash com uma serialização iria fazê-lo.

Respondeu 10/12/2008 em 05:30
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more