Обсуждение: Terminology issue: suffix tree

Поиск
Список
Период
Сортировка

Terminology issue: suffix tree

От
Alexander Korotkov
Дата:
Hackers,

we have SP-GiST opclass called suffix tree. Apparently is NOT suffix tree.
In suffix tree we insert every suffix of source string into the tree.
Actually opclass implemented radix tree or patricia tree.
Likely we need a patch to rename it in all the places it mentioned.

------
With best regards,
Alexander Korotkov.

Re: Terminology issue: suffix tree

От
Alexander Korotkov
Дата:
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
Hackers,

we have SP-GiST opclass called suffix tree. Apparently is NOT suffix tree.

To be clear: not opclass name itself, but comments, readmes and docs are affected.
 
In suffix tree we insert every suffix of source string into the tree.
Actually opclass implemented radix tree or patricia tree.
Likely we need a patch to rename it in all the places it mentioned.

Patch is attached. Apparently, we have same issue in contrib/unaccent.

------
With best regards,
Alexander Korotkov.
Вложения

Re: Terminology issue: suffix tree

От
Heikki Linnakangas
Дата:
On 06.05.2013 14:10, Alexander Korotkov wrote:
> On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov<aekorotkov@gmail.com>wrote:
>> In suffix tree we insert every suffix of source string into the tree.
>> http://en.wikipedia.org/wiki/Suffix_tree
>> Actually opclass implemented radix tree or patricia tree.
>> http://en.wikipedia.org/wiki/Radix_tree
>> Likely we need a patch to rename it in all the places it mentioned.
>
> Patch is attached.

Thanks, committed.

> Apparently, we have same issue in contrib/unaccent.

Yeah. The data structure in contrib/unaccent seems to be a plain old 
trie, rather than a radix trie, though. According to wikipedia at least, 
the difference is that in a radix tree, the edges are labeled with 
sequences of elements, rather than single elements. Want to patch that too?

- Heikki

Re: Terminology issue: suffix tree

От
Alexander Korotkov
Дата:
On Wed, May 8, 2013 at 3:50 PM, Heikki Linnakangas <hlinnakangas@vmware.com> wrote:
On 06.05.2013 14:10, Alexander Korotkov wrote:
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov<aekorotkov@gmail.com>wrote:
In suffix tree we insert every suffix of source string into the tree.

http://en.wikipedia.org/wiki/Suffix_tree
Actually opclass implemented radix tree or patricia tree.
http://en.wikipedia.org/wiki/Radix_tree
Likely we need a patch to rename it in all the places it mentioned.

Patch is attached.

Thanks, committed.

Thanks!
 
Apparently, we have same issue in contrib/unaccent.

Yeah. The data structure in contrib/unaccent seems to be a plain old trie, rather than a radix trie, though. According to wikipedia at least, the difference is that in a radix tree, the edges are labeled with sequences of elements, rather than single elements. Want to patch that too?

Agree, trie is most comforming term here. Patch is attached.

------
With best regards,
Alexander Korotkov.
Вложения

Re: Terminology issue: suffix tree

От
Heikki Linnakangas
Дата:
On 08.05.2013 15:49, Alexander Korotkov wrote:
> On Wed, May 8, 2013 at 3:50 PM, Heikki Linnakangas
> <hlinnakangas@vmware.com>wrote:
>
>> Yeah. The data structure in contrib/unaccent seems to be a plain old trie,
>> rather than a radix trie, though. According to wikipedia at least, the
>> difference is that in a radix tree, the edges are labeled with sequences of
>> elements, rather than single elements. Want to patch that too?
>
> Agree, trie is most comforming term here. Patch is attached.

Ok, applied.

- Heikki