Feature request: add method to get all valid words within a given string

[gonzedge]

As mentioned by @darkogj on Twitter, there is no current way to find out if a given string contains a valid word from a given dictionary. In @darkogj's words:

... The challenge is, if you have 'aheyb' as the target word, for the gem to recognize 'hey' is a word although it's not at the beginning of the string.

I made a short implementation of this for uncompressed tries, but it hasn't been thoroughly tested or benchmarked and it isn't compatible with compressed tries. Those need to be taken care of before integrating it into the gem.

[gonzedge]

Also, I'm not sure what such a method should be called. #words? #words_within?

Naming is hard.

[darkogj]

Cool! I can see the way this can be accomplished is by basically:

• Separating the string into sub-strings
• Feeding each sub-string into the trie algo

I'm not familiar with the trie algo and all its variations, but basically, you can do only exact match testing (word against word), right? So in order for this feature to be implemented, basically you'll have to separate the word into substrings and test each word with .word?

I think a good name would be #has_any_substring? , #any_substring? or something like that.

[darkogj]

I explored the Aho-Corasick matcher (there are only 2 Ruby gems for this - I've used https://github.com/altmetric/aho_corasick_matcher) and it's pretty much destroys the trie algorithm for substring matching. I've tested it against 100,000 random words and it gave me the results in 1.5 seconds vs. 8.5 for rambling_trie (20+ seconds for the ordinary trie gem that's most popular on RubyGems). Not only that, it gave me ALL the sub-strings, pretty amazing.

You may want to consider implementing this in your library for some of the functionalities, or maybe start another one, it's very weird not many libs are there for Ruby for this.

[darkogj]

Btw, one guy on SO did a benchmark against other gems:

http://stackoverflow.com/a/41523304/4214184

and it seems in the non-tail version, your gem is 4x slower than trie/triez. For the tail case, the results were comparable.

Also he suggested a way to implement prefix matching feature with some code.

[gonzedge]

@darkogj Makes sense. This implementation is pure Ruby, so it should be slower, even with an optimal algorithm.

Also, that benchmark is great!!

I've been shying away from dropping down to C for a while, especially since not a lot of people seemed to be using this gem in the past, but it looks like the time has come. I might explore that in the near feature.

This might be a good chance for me to get my hands dirty with Rust 🤓 .