{"action":"created","issue":{"url":"https://api.github.com/repos/skroutz/string_metric/issues/20","labels_url":"https://api.github.com/repos/skroutz/string_metric/issues/20/labels{/name}","comments_url":"https://api.github.com/repos/skroutz/string_metric/issues/20/comments","events_url":"https://api.github.com/repos/skroutz/string_metric/issues/20/events","html_url":"https://github.com/skroutz/string_metric/pull/20","id":67944032,"number":20,"title":"Introduce a new variation of the Levenshtein algorithm","user":{"login":"freestyl3r","id":2126390,"avatar_url":"https://avatars.githubusercontent.com/u/2126390?v=3","gravatar_id":"","url":"https://api.github.com/users/freestyl3r","html_url":"https://github.com/freestyl3r","followers_url":"https://api.github.com/users/freestyl3r/followers","following_url":"https://api.github.com/users/freestyl3r/following{/other_user}","gists_url":"https://api.github.com/users/freestyl3r/gists{/gist_id}","starred_url":"https://api.github.com/users/freestyl3r/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/freestyl3r/subscriptions","organizations_url":"https://api.github.com/users/freestyl3r/orgs","repos_url":"https://api.github.com/users/freestyl3r/repos","events_url":"https://api.github.com/users/freestyl3r/events{/privacy}","received_events_url":"https://api.github.com/users/freestyl3r/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-04-12T19:00:37Z","updated_at":"2015-05-23T08:51:52Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/skroutz/string_metric/pulls/20","html_url":"https://github.com/skroutz/string_metric/pull/20","diff_url":"https://github.com/skroutz/string_metric/pull/20.diff","patch_url":"https://github.com/skroutz/string_metric/pull/20.patch"},"body":"#### Introduction\r\n\r\nDisclaimer: the interface for this implementation is not compatible with the one this gem enforces, so it might not be a good candidate for merging. Nevertheless, it's a very good representation of what can be achieved using a more efficient approach.\r\n\r\nTrie (or radix / prefix tree) is a data structure with performance characteristics that can even beat those of a hash. (search misses for example don't have to examine the whole key, therefore completing in sub-linear time)\r\nWhen traversing a trie we can find all keys / words with the same prefix. We can exploit this property to feed the Levenshtein algorithm with all the words that contain the same prefix, in order.\r\nWe only to have to calculate the difference between the previous smaller prefix word instead of doing the whole computation again.\r\n\r\nFor more info: http://stevehanov.ca/blog/index.php?id=114\r\n\r\n#### Using the algorithm\r\n\r\nThis is where the interface differs from the rest implementations. Instead of 2 words to match, the method expects 1 word and a prebuilt Trie data structure. `distance(from, TrieNode, options = {})`\r\nBuilding the Trie tree is a matter of simply inserting the words we want to match against (e.x. dictionary) in any order we have them.\r\nAssuming we already have the words in the `dictionary` array, the building of the Trie will look similar to this:\r\n\r\n    trie = StringMetric::Levenshtein::TrieNode.new\r\n    dictionary.each do |word| \r\n      trie.insert(word)\r\n    end\r\n\r\nThis implementation is very good when we want to quickly get a list of all the words that have a set maximum_distance compared to ours. e.x.: `StringMetric::Levenshtein::TrieRadixTree.distance('case', products, max_distance: 1)`\r\n\r\nIt should also be very fast when we watch to match on longer sequence of words since, if we reach a word that exceeds our max_distance, all the rest nodes starting with that same prefix are discarded.\r\n\r\n#### Benchmark results\r\n\r\nSo how much faster is this strategy versus randomly feeding words to Levenshtein?\r\nHere are some results using 10 words and matching them with a dictionary of `234937` words on my system's `/usr/share/dict/words` file.\r\n\r\nImplementation                                      | User      | Real\r\n------------------------------------------------- |-----------------|-----------\r\ntwo_matrix_rows_v2 implementation     | 108.520000 | (108.629240)\r\ntwo_matrix_rows_ext implementation    | 6.170000     | (  6.165258)\r\ntrie_radix_tree implementation              | 1.570000     | (  1.574100)\r\ntrie_radix_tree_ext implementation       | 0.080000     | (  0.077781)\r\n\r\n#### Downsides\r\n\r\nFirst there is the disparity in the interface. A different set of tests is required, although i personally tested it against the reference python implementation and the one from the `text` gem.\r\n\r\nSecond, there is a time and space cost associated with populating the Trie data structure.\r\nOn my machine the time cost, far outweighed the actual computation of the algorithm. ~1.8 secs to generate the tree, 0.07 sec to run the benchmark.\r\n\r\nIf one could afford even less flexibility, the populating step could be done inside the native extension written in C.\r\nThe problem with that is the big space requirements of the data structure. Each node must hold an array of size as big as the biggest codepoint of the required character set (e.x. 256 for the extended ascii set)\r\nFor the dictionary mentioned above we have 234937 words in 791098 nodes.\r\n791098 nodes * 256 array_bytes = 202521088 bytes = ~200mb ram\r\n\r\nAnd indeed the program occupies around 220mb ram while holding the data structure.\r\nThe real problem comes when you have to support unicode. Assuming unicode requires ~ 65000 codepoints the above calculation becomes:\r\n791098 nodes * 65000 array_bytes = 51421370000 bytes = ~50**gb** ram\r\n\r\nRuby gets around that by using hashes instead of arrays, so it does not have to keep the whole codeset in each node.\r\n\r\nI ventured even further and implemented a [ternary search tree](http://en.wikipedia.org/wiki/Ternary_search_tree) which is a more compact version of tries.\r\nEach node holds 3 other nodes instead of the whole array.\r\nI was able to get the memory usage down to ~160mb but the populating running time cost increased by a lot due to the added complexity.\r\nThat was in ruby, in C it would be faster of course.\r\n"},"comment":{"url":"https://api.github.com/repos/skroutz/string_metric/issues/comments/104869647","html_url":"https://github.com/skroutz/string_metric/pull/20#issuecomment-104869647","issue_url":"https://api.github.com/repos/skroutz/string_metric/issues/20","id":104869647,"user":{"login":"chief","id":22738,"avatar_url":"https://avatars.githubusercontent.com/u/22738?v=3","gravatar_id":"","url":"https://api.github.com/users/chief","html_url":"https://github.com/chief","followers_url":"https://api.github.com/users/chief/followers","following_url":"https://api.github.com/users/chief/following{/other_user}","gists_url":"https://api.github.com/users/chief/gists{/gist_id}","starred_url":"https://api.github.com/users/chief/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/chief/subscriptions","organizations_url":"https://api.github.com/users/chief/orgs","repos_url":"https://api.github.com/users/chief/repos","events_url":"https://api.github.com/users/chief/events{/privacy}","received_events_url":"https://api.github.com/users/chief/received_events","type":"User","site_admin":false},"created_at":"2015-05-23T08:51:52Z","updated_at":"2015-05-23T08:51:52Z","body":"* very nice thought to include this implementation\r\n* I think it will be great to merge it into master\r\n\r\nvery good! \r\n\r\n:+1: "}}