Hi Dave,<br><br>actually I try not to think :)<br><br>Truth to be told I have little experience in the domain, but I have time at my disposal, therefore rather than thinking I simply brute-force the tests and see what comes best. I'd rather not assume, especially performance-wise.<br>
<br>For the prefix / suffix implementation, I'm waiting for a "typical" lexicon to see what comes out first. I'm in the hope than it should not matter, unless I have a glaring bottleneck in the code, but as I said i prefer to measure. Frankly it's the least of my worries since it suffices to reverse the strings to get from one to the other so there is no technical difficulty there.<br>
<br>I know that my trie implementation is probably lacking (as I said, it's naive), so I am trying to see what is the state of the art on storing dictionaries and notably how to "pack" tries to get a smaller memory foot-print and a faster query. The idea is to gather the various approaches, implement them and benchmark them, and I'll see what comes on top.<br>
<br>I'd really like to see this hash-trie implementation if you could send it to me. I don't mind having to read C / C++ code as long as it's not obfuscated, in fact I'll probably feel much more at ease than decoding the scientific paper I got on the automaton theory and which took me a good week to implement :)<br>
<br>Thanks,<br>Matthieu.<br><br><div class="gmail_quote">2010/11/22 David Tweed <span dir="ltr"><<a href="mailto:david.tweed@gmail.com">david.tweed@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
On Sun, Nov 21, 2010 at 7:58 PM, Matthieu Monrocq<br>
<<a href="mailto:matthieu.monrocq@gmail.com">matthieu.monrocq@gmail.com</a>> wrote<br>
<div class="im">>> We had a discussion a month ago I think about the Spell Correction<br>
>> algorithm which was used in CLang, notably for auto-completion, based on the<br>
>> Levenstein distance.<br>
<br>
</div>I presume you've thought about whether suffix-tries and prefix-tries<br>
would work for the case of typos on computer identifiers?<br>
<div class="im"><br>
> - a good Trie implementation, or hints in how to implement one. A Trie seems<br>
> to be the best index (quite compact yet ordered), however I only have a<br>
> naive implementation at the moment.<br>
<br>
</div>I've got a hash-trie implementation (the datastructure that is used,<br>
eg, to store the dictionary of hypenation exceptions in TeX) in C++<br>
that's heavily designed for small alphabets and integer "payloads", so<br>
it's unlikely to be directly suitable, but you can have  a look at it<br>
if you like. (Drop me a personal email.)<br>
<font color="#888888"><br>
--<br>
cheers, dave tweed__________________________<br>
computer vision reasearcher: <a href="mailto:david.tweed@gmail.com">david.tweed@gmail.com</a><br>
"while having code so boring anyone can maintain it, use Python." --<br>
attempted insult seen on slashdot<br>
</font></blockquote></div><br>