{"action":"created","issue":{"url":"https://api.github.com/repos/phosphorjs/phosphide/issues/16","labels_url":"https://api.github.com/repos/phosphorjs/phosphide/issues/16/labels{/name}","comments_url":"https://api.github.com/repos/phosphorjs/phosphide/issues/16/comments","events_url":"https://api.github.com/repos/phosphorjs/phosphide/issues/16/events","html_url":"https://github.com/phosphorjs/phosphide/issues/16","id":121535757,"number":16,"title":"Command Palette Fuzzy Matching","user":{"login":"dwillmer","id":2343358,"avatar_url":"https://avatars.githubusercontent.com/u/2343358?v=3","gravatar_id":"","url":"https://api.github.com/users/dwillmer","html_url":"https://github.com/dwillmer","followers_url":"https://api.github.com/users/dwillmer/followers","following_url":"https://api.github.com/users/dwillmer/following{/other_user}","gists_url":"https://api.github.com/users/dwillmer/gists{/gist_id}","starred_url":"https://api.github.com/users/dwillmer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dwillmer/subscriptions","organizations_url":"https://api.github.com/users/dwillmer/orgs","repos_url":"https://api.github.com/users/dwillmer/repos","events_url":"https://api.github.com/users/dwillmer/events{/privacy}","received_events_url":"https://api.github.com/users/dwillmer/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-12-10T17:18:06Z","updated_at":"2015-12-10T19:16:06Z","closed_at":null,"body":"As part of the command palette work, we're going to need to perform fuzzy matching on user inputs. This issue is for discussing the various packages available / whether we should write our own.\r\n\r\n# fuzzy\r\n\r\n[[https://www.npmjs.com/package/fuzzy]]\r\n[[https://github.com/mattyork/fuzzy]]\r\n\r\n```\r\nnpm install --save fuzzy\r\n```\r\n\r\nSummary - seems simple to set up and use, but also lacking the more advanced features in other packages:\r\n\r\n```javascript\r\nvar fuzzy = require('fuzzy');\r\nvar data = ['alpha', 'altitude', 'alien', 'bob'];\r\nvar results = fuzzy.filter('al', data);\r\nvar matches = results.map(function(el) { return el.string; });\r\nconsole.log(matches); // ['alpha', 'altitude', 'alien']\r\n```\r\n\r\nallows you to wrap the matching characters with `pre` and `post` tags\r\n(eg, in order to highlight the matching characters):\r\n\r\n```javascript\r\nvar data = ['alpha', 'altitude', 'alien', 'bob'];\r\nvar options = { pre: '<b>', post: '</b>' };\r\nvar results = fuzzy.filter('al', data, options);\r\nconsole.log(results);\r\n```\r\ngives\r\n```\r\n[\r\n  {string: '<b>al</b>pha', index: 0, score: 2, original: 'alpha'},\r\n  {string: '<b>al</b>titude', index: 1, score: 2, original: 'altitude'},\r\n  {string: '<b>al</b>ien', index: 2, score: 2, original: 'alien'}\r\n]\r\n```\r\nIt also allows you to provide a function for extracting the string to search\r\nfrom an object:\r\n```javascript\r\nvar items = [{the_string: 'alien'}, {the_string: 'bob'}];\r\nvar options = {\r\n  extract: function(el) { return el.the_string; }\r\n};\r\n```\r\nhowever, it doesn't appear to support levenstein distance or custom routines:\r\n```javascript\r\nvar data = ['alpha', 'alps'];\r\nfuzzy.filter('alpi', data); // empty array returned\r\n```\r\n\r\nIt also *does* have a case-sensitivity option, but it's not documented on the front page, or used in the examples, and requires searching through the code in order to find it. not a good impression for the feature most people will want to try/set for the simple searches.\r\n\r\n# fuzzysearch-js\r\n\r\n[[https://www.npmjs.com/package/fuzzysearch-js]]\r\n[[https://github.com/unlooped/FuzzySearchJS]]\r\n\r\nseems more complicated to set up and use, but allows easy customisation of the search routines, and includes a module system to use pre-packaged modules\r\nfor the more advanced searches, such as levenstein distance:\r\n\r\n(this example taken directly from the npm/github front page)\r\n```javascript\r\nvar FuzzySearch = require('fuzzysearch-js');\r\nvar levenshteinFS = require('fuzzysearch-js/js/modules/LevenshteinFS');\r\nvar indexOfFS = require('fuzzysearch-js/js/modules/IndexOfFS');\r\nvar wordCountFS = require('fuzzysearch-js/js/modules/WordCountFS');\r\n\r\nvar data = ['Hydrogen','Helium','Lithium','Beryllium'];\r\n\r\nvar fuzzySearch = new FuzzySearch(data, {'minimumScore': 300});\r\nfuzzySearch.addModule(levenshteinFS({'maxDistanceTolerance': 3, 'factor': 3}));\r\nfuzzySearch.addModule(indexOfFS({'minTermLength': 3, 'maxIterations': 500, 'factor': 3}));\r\nfuzzySearch.addModule(wordCountFS({'maxWordTolerance': 3, 'factor': 1}));\r\n\r\nvar result = fuzzySearch.search('Hlium');\r\nconsole.log(result);\r\n```\r\nreturns\r\n```\r\n[ { score: 590,\r\n  details: [ [Object], [Object], [Object] ],\r\n  value: 'Helium' },\r\n{ score: 340,\r\n  details: [ [Object], [Object], [Object] ],\r\n  value: 'Beryllium' } ]\r\n```\r\nThis is quite a bit of extra setup, but gives a lot of configurability.\r\n\r\nThe whole system revolves around a general score which is calculated from the scores\r\nafter running all the added modules. This appeals to me as we can add our own\r\nmodules, or just tweak the scoring system to suit our own needs.\r\n\r\nNegatives: There's no performance benchmarks, and the tests aren't comprehensive.\r\n\r\n\r\n# fuzzy-filter\r\n\r\n[[https://www.npmjs.com/package/fuzzy-filter]]\r\n[[https://github.com/stratuseditor/fuzzy-filter]]\r\n\r\n```javascript\r\nvar fuzzy = require('fuzzy-filter')\r\nfuzzy(\"alp\", [\"altitude\", \"alps\"]) // [\"alps\"]\r\n```\r\n\r\nSupports case insensitive searches, and orders the results nicely, but is\r\nquite simplistic and doesn't include a full scoring system like fuzzysearch-js. \r\n\r\n# fuzzaldrin\r\n\r\n[[https://www.npmjs.com/package/fuzzaldrin]]\r\n[[https://github.com/atom/fuzzaldrin]]\r\n\r\nThe fuzzy matcher written for Github's Atom editor. Seems fairly good - has\r\nseparate scoring and filtering modules, and returns decent results.\r\n\r\nNegatives - a lot of the 'internals' are very hard-coded. For example in the\r\nscorer module, there's lines like:\r\n\r\n```coffeescript\r\nif indexInString is 0 or ...:\r\n  characterScore += 0.8\r\n```\r\n\r\nclearly scoring works along these lines, but there's no way to tweak the `0.8`\r\nin this case, without just copying the whole module - it's not been written \r\nto be configurable. On the other hand, these values are probably hand-tweaked\r\nfor a code editor, so they might be useful to us.\r\n\r\nFuzzaldrin also has a benchmark setup (`npm run benchmark`), which is a very\r\ngood sign.\r\n\r\nIn general i think that it's a suitable module, but the hard-coding is a huge negative.\r\nAlso, being part of Atom means it's written in CoffeeScript, which is just terrible.\r\n\r\n# Summary\r\n\r\nIn general, I think fuzzysearch-js is the best candidate as it's modular and\r\nextensible.\r\n\r\nAtom's fuzzaldrin is also a good contender, and is the only package to have usable\r\nbenchmarks, but the hard-coding is worrying."},"comment":{"url":"https://api.github.com/repos/phosphorjs/phosphide/issues/comments/163723012","html_url":"https://github.com/phosphorjs/phosphide/issues/16#issuecomment-163723012","issue_url":"https://api.github.com/repos/phosphorjs/phosphide/issues/16","id":163723012,"user":{"login":"sccolbert","id":137289,"avatar_url":"https://avatars.githubusercontent.com/u/137289?v=3","gravatar_id":"","url":"https://api.github.com/users/sccolbert","html_url":"https://github.com/sccolbert","followers_url":"https://api.github.com/users/sccolbert/followers","following_url":"https://api.github.com/users/sccolbert/following{/other_user}","gists_url":"https://api.github.com/users/sccolbert/gists{/gist_id}","starred_url":"https://api.github.com/users/sccolbert/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sccolbert/subscriptions","organizations_url":"https://api.github.com/users/sccolbert/orgs","repos_url":"https://api.github.com/users/sccolbert/repos","events_url":"https://api.github.com/users/sccolbert/events{/privacy}","received_events_url":"https://api.github.com/users/sccolbert/received_events","type":"User","site_admin":false},"created_at":"2015-12-10T19:16:05Z","updated_at":"2015-12-10T19:16:05Z","body":"Thanks for the benchmarks!"}}