{"id":11049,"date":"2022-12-31T13:43:38","date_gmt":"2022-12-31T18:43:38","guid":{"rendered":"https:\/\/irreal.org\/blog\/?p=11049"},"modified":"2022-12-31T13:43:38","modified_gmt":"2022-12-31T18:43:38","slug":"checking-a-word-list","status":"publish","type":"post","link":"https:\/\/irreal.org\/blog\/?p=11049","title":{"rendered":"Checking A Word List"},"content":{"rendered":"<p>Daniel Lemire has a <a href=\"https:\/\/lemire.me\/blog\/2022\/12\/30\/quickly-checking-that-a-string-belongs-to-a-small-set\/\">post that poses an interesting challenge<\/a>. Suppose you have a list of words\u2014Lemire uses \u201cftp\u201d, \u201cfile\u201d, \u201chttp\u201d, \u201chttps\u201d, \u201cws\u201d, \u201cwss\u201d\u2014and want to check if some other word is in the list.<\/p>\n<p>Unless you believe in Zawinski\u2019s law, you might choose regular expressions, especially if you\u2019re writing in Elisp. But as Lemire points out, that\u2019s going to be pretty slow. My first thought was to use <a href=\"https:\/\/www.gnu.org\/software\/emacs\/manual\/html_node\/elisp\/Regexp-Functions.html#index-regexp_002dopt\">regexp-opt<\/a> to generate an optimized regular expression. For the list above, regexp-opt returns the regex <code>\"\\\\(?:f\\\\(?:ile\\\\|tp\\\\)\\\\|https?\\\\|wss?\\\\)\"<\/code>, which will be faster than the obvious regexp but probably still not that fast if the check is going to be made many times.<\/p>\n<p>Lemire offers some other solutions\u2014in C++\u2014including the obvious one of just sequentially checking the list. For a longer list, that could be sped up with a binary search but probably wouldn\u2019t help much with the short list we have. He also offers some other solutions based on padding the input string. He has some benchmark results if you\u2019re interested in the relative times.<\/p>\n<p>One solution that he doesn\u2019t mention is the one I would think of first: check inclusion with some sort of hashing operation. The obvious solution of that sort is to just put the list words in a hash table and check the input word by looking it up. That\u2019s going to be very fast, especially if the list is long.<\/p>\n<p>Perfect hashing seems like another good solution for a short list and will be fast to eliminate a candidate word but if you get a hit, you still have to check for a match. In any event, since the word list is known beforehand, you can adjust whatever hashing strategy you use to be as fast as possible. String comparisons are probably going to be the bottle neck is any reasonable solution so it\u2019s important that the solution minimize those as much as possible.<\/p>\n<p>It\u2019s a nice problem and well worth thinking about.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Daniel Lemire has a post that poses an interesting challenge. Suppose you have a list of words\u2014Lemire uses \u201cftp\u201d, \u201cfile\u201d, \u201chttp\u201d, \u201chttps\u201d, \u201cws\u201d, \u201cwss\u201d\u2014and want to check if some other word is in the list. Unless you believe in Zawinski\u2019s &hellip; <a href=\"https:\/\/irreal.org\/blog\/?p=11049\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[18],"class_list":["post-11049","post","type-post","status-publish","format-standard","hentry","category-programming","tag-emacs"],"_links":{"self":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/11049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11049"}],"version-history":[{"count":1,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/11049\/revisions"}],"predecessor-version":[{"id":11050,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/11049\/revisions\/11050"}],"wp:attachment":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}