{"action":"created","issue":{"url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/13","repository_url":"https://api.github.com/repos/wolfgarbe/SymSpell","labels_url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/13/labels{/name}","comments_url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/13/comments","events_url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/13/events","html_url":"https://github.com/wolfgarbe/SymSpell/pull/13","id":278011220,"number":13,"title":"Separated below threshold words","user":{"login":"softwx","id":2808068,"avatar_url":"https://avatars3.githubusercontent.com/u/2808068?v=4","gravatar_id":"","url":"https://api.github.com/users/softwx","html_url":"https://github.com/softwx","followers_url":"https://api.github.com/users/softwx/followers","following_url":"https://api.github.com/users/softwx/following{/other_user}","gists_url":"https://api.github.com/users/softwx/gists{/gist_id}","starred_url":"https://api.github.com/users/softwx/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/softwx/subscriptions","organizations_url":"https://api.github.com/users/softwx/orgs","repos_url":"https://api.github.com/users/softwx/repos","events_url":"https://api.github.com/users/softwx/events{/privacy}","received_events_url":"https://api.github.com/users/softwx/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":1,"created_at":"2017-11-30T06:24:27Z","updated_at":"2017-11-30T10:45:05Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/wolfgarbe/SymSpell/pulls/13","html_url":"https://github.com/wolfgarbe/SymSpell/pull/13","diff_url":"https://github.com/wolfgarbe/SymSpell/pull/13.diff","patch_url":"https://github.com/wolfgarbe/SymSpell/pull/13.patch"},"body":"Separated below threshold words from above threshold words and deletes\r\nAdded parameter checks for constructor\r\nMinor optiimisations in Lookup\r\nAdded percent increase/decrease of benchmark averages.\r\n\r\nThe main thing in this commit is the separation of below threshold words. That will make the remaining optimisations easier to implement. Plus, there is no benefit in having below threshold words co-mingled with correct spelling above threshold words, and delete words."},"comment":{"url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/comments/348151686","html_url":"https://github.com/wolfgarbe/SymSpell/pull/13#issuecomment-348151686","issue_url":"https://api.github.com/repos/wolfgarbe/SymSpell/issues/13","id":348151686,"user":{"login":"wolfgarbe","id":7057583,"avatar_url":"https://avatars0.githubusercontent.com/u/7057583?v=4","gravatar_id":"","url":"https://api.github.com/users/wolfgarbe","html_url":"https://github.com/wolfgarbe","followers_url":"https://api.github.com/users/wolfgarbe/followers","following_url":"https://api.github.com/users/wolfgarbe/following{/other_user}","gists_url":"https://api.github.com/users/wolfgarbe/gists{/gist_id}","starred_url":"https://api.github.com/users/wolfgarbe/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wolfgarbe/subscriptions","organizations_url":"https://api.github.com/users/wolfgarbe/orgs","repos_url":"https://api.github.com/users/wolfgarbe/repos","events_url":"https://api.github.com/users/wolfgarbe/events{/privacy}","received_events_url":"https://api.github.com/users/wolfgarbe/received_events","type":"User","site_admin":false},"created_at":"2017-11-30T10:45:05Z","updated_at":"2017-11-30T10:45:05Z","author_association":"OWNER","body":"**initialCapacity**\r\n\r\n`this.dictionary = new Dictionary<string, DictionaryItem>(initialCapacity * (1 + Math.Min(4, maxDictionaryEditDistance)/2));`\r\n\r\nI'm not sure I fully understand this. The number of dictionary items equals the number of unique terms + the number of n-deletes from those terms (n<=maxEditDistance).\r\nThe user typically doesn't know about the deletes and how to calculate their number. So probably the user should for the initialCapacity just specify the expected number of unique terms and we calculate the number of deletes and thus the true capacity of the dictionary from this.\r\n\r\nThe number x of deletes for a single dictionary entry depends on the maximum edit distance: x=n for edit distance=1, x=n*(n-1)/2 for edit distance=2, x=n!/d!/(n-d)! for edit distance=d (combinatorics: k out of n combinations without repetitions, and k=n-d),\r\nE.g. for a maximum edit distance of 2 and an average word length of 5 and 100,000 dictionary entries we need to additionally store 1,500,000 deletes.\r\n\r\nSo perhaps we should provide a function NumberOfDeletesFromUniqueWords using the above formulas. We can use the function internally to set the right initial capacity of the dictionary and we can make also public for the user in case he wants to know beforehand what size to expect. What do you think?"}}
{"actor":{"display_login":"wolfgarbe"}}