search

quek / nunumo

3 stars 0 forks source link

status? #1

Open danlentz opened 10 years ago

danlentz commented 10 years ago

long ago I kept watch as you were coding nunumo but, at least for me, there remained issues preventing correct operation on my SBCL environment. curious as to status -- were these known issues, Were there ongoing unresolved issues when you left off development? Was it working for you?

quek commented 10 years ago

I am sorry. I currently left off development.

danlentz commented 10 years ago

Yes, don"t be sorry it was even so a pleasure to observe the process and study your approach to various situations.

Dan

On Saturday, February 15, 2014, Yoshinori Tahara notifications@github.com wrote:

I am sorry. I currently left off development.

— Reply to this email directly or view it on GitHubhttps://github.com/quek/nunumo/issues/1#issuecomment-35148475 .

quek commented 10 years ago

Thanks. Your cl-ctrie seems good.

danlentz commented 10 years ago

Thank you, I admire your work as well. Ctrie is interesting but also very complicated. I have recently been working on implementing "Patricia" trie and have found it to be a very versatile approach, yet retains elegant simplicity. I think it may possibly be better than any other tree, trie, hash, ... I have found.

On Saturday, February 15, 2014, Yoshinori Tahara notifications@github.com wrote:

Thanks. Your cl-ctrie seems good.

— Reply to this email directly or view it on GitHubhttps://github.com/quek/nunumo/issues/1#issuecomment-35148606 .

quek commented 10 years ago

Oh! Now I am interested in trie tree and study double array. I am looking forward to your work. Have a good hack!

danlentz commented 10 years ago

Have you seen the double array implemented by user Sile within his library CL-DAWG? I think very much of his work and spent quite some effort using google translate to understand his articles. Unfortunately, the translation was very, very poor -- just random words.

One thing I was trying to understand was if it was possible to dynamically extend a DoubleArray or if it is limited to static index only. That is true for v1 and v2 but perhaps he overcame? It was not clear what he was saying about his final buffered version. Google translate gets F for grade in Japanese class!

Dan

On Saturday, February 15, 2014, Yoshinori Tahara notifications@github.com wrote:

Oh! Now I am interested in trie tree and study double array. I am looking forward to your work. Have a good hack!

— Reply to this email directly or view it on GitHubhttps://github.com/quek/nunumo/issues/1#issuecomment-35150346 .

quek commented 10 years ago

I don't read his double array code.

It was not clear what he was saying about his final buffered version.

Which article?

danlentz commented 10 years ago

I wasn't able to find the exact article I was referring to (it's really difficult site for English speakers :) I did find two related articles you might be interested in since they show demonstration and performance of his DA. I'm very sure there were 1-2 more articles on there where he talked about CL-dawg and also it looked like he gave an overview of how it had progressed after several versions later.

http://d.hatena.ne.jp/sile/20090716/1247691941

http://d.hatena.ne.jp/sile/20101101/1288552815

I read through you DA and trie and at first look it is clear and helpful to understand do you track statistics of how many branches had to be moved, etc? Of course DA is primarily optimized for lookup and space, so 2.0 seconds to write 66000 nodes is usable. Sile did spend a lot of time fine tuning his DA so I would like to see you guys race!

Dan

On Saturday, February 15, 2014, Yoshinori Tahara notifications@github.com wrote:

I don't read his double array code.

It was not clear what he was saying about his final buffered version.

Which article?

— Reply to this email directly or view it on GitHubhttps://github.com/quek/nunumo/issues/1#issuecomment-35155151 .

quek commented 10 years ago

Thanks for url of articles.

https://github.com/sile/cl-dawg

cl-dawg receives to the static input key set, and maps a unique ID to each key. Each key must be unique key input set and is already sorted.

The double array in cl-dawg is seems to have made to build DAWG from sorted key set. Maybe it is not optimized for dynamic extend.

I try to write double array to file. After that, I'll try to implement the statistics. It is interesting.

danlentz commented 10 years ago

It is understandable for it be static, but I appreciate your DA because it is not. CL-DAWG I think was designed to favor performance over general utility. keep me posted!

quek commented 10 years ago

I've implemented by referring to this page http://linux.thai.net/~thep/datrie/datrie.html I'll keep you posted. Thanks!

danlentz commented 10 years ago

I just found this DA which seems to be much clearer than the one he has incorporated into CL-DAWG. I had not seen this one before. I have been thinking about what cases I might run into where it wouldn't be a problem about the static, expensive, write operation and the priority would be speed & storage.... It is a fact of life that situations that specific loses some generality in the process. But as a secondary, persistent, optimized "tagged" version of my Patricia trie (which updates using the manner of "patches" of related updates. So, for the ROOT-LAYER-CONTEXT the argument could be made to use it:)

danlentz commented 10 years ago

I apologize I seem to not gave given the link whoops!

https://github.com/sile/dabase