Обсуждение: Terminology issue: suffix tree
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.
On Sat, May 4, 2013 at 10:27 PM, Alexander Korotkov <aekorotkov@gmail.com> wrote:
------
With best regards,
Alexander Korotkov.
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.
Вложения
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
On Wed, May 8, 2013 at 3:50 PM, Heikki Linnakangas <hlinnakangas@vmware.com> wrote:
------
With best regards,
Alexander Korotkov.
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!
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?Apparently, we have same issue in contrib/unaccent.
Agree, trie is most comforming term here. Patch is attached.
With best regards,
Alexander Korotkov.
Вложения
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