fork(1) download 
  1. var PhraseSearch = function () {   
  2.     var Trie = function () {
  3.         this.phraseWordCount = {};
  4.         this.children = {};
  5.     };
  6.  
  7.     Trie.prototype.addPhraseWord = function (phrase, word) {
  8.         if (word !== '') {
  9.             var first = word.charAt(0);
  10.  
  11.             if (!this.children.hasOwnProperty(first)) {
  12.                 this.children[first] = new Trie();
  13.             }
  14.             var rest = word.substring(1);
  15.             this.children[first].addPhraseWord(phrase, rest);
  16.         }
  17.         if (!this.phraseWordCount.hasOwnProperty(phrase)) {
  18.             this.phraseWordCount[phrase] = 0;
  19.         }
  20.         this.phraseWordCount[phrase]++;
  21.     };
  22.  
  23.     Trie.prototype.getPhraseWordCount = function (prefix) {
  24.         if (prefix !== '') {
  25.             var first = prefix.charAt(0);
  26.  
  27.             if (this.children.hasOwnProperty(first)) {
  28.                 var rest = prefix.substring(1);
  29.                 return this.children[first].getPhraseWordCount(rest);
  30.             } else {
  31.                 return {};
  32.             }
  33.         } else {
  34.             return this.phraseWordCount;
  35.         }
  36.     }
  37.  
  38.     this.trie = new Trie();
  39. }
  40.  
  41. PhraseSearch.prototype.addPhrase = function (phrase) {
  42.     var words = phrase.trim().toLowerCase().split(/\s+/);
  43.     words.forEach(function (word) {
  44.         this.trie.addPhraseWord(phrase, word);
  45.     }, this);
  46. }
  47.  
  48. PhraseSearch.prototype.search = function (query) {
  49.     var answer = {};
  50.     var phraseWordCount = this.trie.getPhraseWordCount('');
  51.     for (var phrase in phraseWordCount) {
  52.         if (phraseWordCount.hasOwnProperty(phrase)) {
  53.             answer[phrase] = true;
  54.         }
  55.     }
  56.  
  57.     var prefixes = query.trim().toLowerCase().split(/\s+/);
  58.  
  59.     prefixes.sort();
  60.     prefixes.reverse();
  61.  
  62.     var prevPrefix = '';
  63.     var superprefixCount = 0;
  64.  
  65.     prefixes.forEach(function (prefix) {
  66.         if (prevPrefix.indexOf(prefix) !== 0) {
  67.             superprefixCount = 0;
  68.         }
  69.         phraseWordCount = this.trie.getPhraseWordCount(prefix);
  70.  
  71.         function phraseMatchedWordCount(phrase) {
  72.             return phraseWordCount.hasOwnProperty(phrase) ? phraseWordCount[phrase] - superprefixCount : 0;
  73.         }
  74.  
  75.         for (var phrase in answer) {
  76.             if (answer.hasOwnProperty(phrase) && phraseMatchedWordCount(phrase) < 1) {
  77.                 delete answer[phrase];
  78.             }
  79.         }
  80.  
  81.         prevPrefix = prefix;
  82.         superprefixCount++;
  83.     }, this);
  84.  
  85.     return answer;
  86. }
  87.  
  88. function test() {
  89.     var phraseSearch = new PhraseSearch();
  90.  
  91.     var phrases = [
  92.         'Stack Overflow',
  93.         'Math Overflow',
  94.         'Super User',
  95.         'Webmasters',
  96.         'Electrical Engineering',
  97.         'Programming Jokes',
  98.         'Programming Puzzles',
  99.         'Geographic Information Systems',
  100.         'Programming Puzzles Overflow'
  101.     ];
  102.  
  103.     phrases.forEach(phraseSearch.addPhrase, phraseSearch);
  104.  
  105.     var queries = {
  106.         's':       'Stack Overflow, Super User, Geographic Information Systems',
  107.         'web':     'Webmasters',
  108.         'over':    'Stack Overflow, Math Overflow, Programming Puzzles Overflow',
  109.         'super u': 'Super User',
  110.         'user s':  'Super User',
  111.         'e e':     'Electrical Engineering',
  112.         'p':       'Programming Jokes, Programming Puzzles, Programming Puzzles Overflow',
  113.         'p p':     'Programming Puzzles, Programming Puzzles Overflow',
  114.         'e p':     '',
  115.         'p o o':   ''
  116.     };
  117.  
  118.     for(var query in queries) {
  119.         if (queries.hasOwnProperty(query)) {
  120.             var expected = queries[query];
  121.             var actual = Object.keys(phraseSearch.search(query)).join(', ');
  122.  
  123.             print('query: ' + query);
  124.             print('expected: ' + expected);
  125.             print('actual: ' + actual);
  126.             print('');
  127.         }
  128.     }
  129. }
  130.  
  131. test();
Success #stdin #stdout 0.01s 29992KB
comments (?)
stdin 
Standard input is empty
stdout 
query: s
expected: Stack Overflow, Super User, Geographic Information Systems
actual: Stack Overflow, Super User, Geographic Information Systems

query: web
expected: Webmasters
actual: Webmasters

query: over
expected: Stack Overflow, Math Overflow, Programming Puzzles Overflow
actual: Stack Overflow, Math Overflow, Programming Puzzles Overflow

query: super u
expected: Super User
actual: Super User

query: user s
expected: Super User
actual: Super User

query: e e
expected: Electrical Engineering
actual: Electrical Engineering

query: p
expected: Programming Jokes, Programming Puzzles, Programming Puzzles Overflow
actual: Programming Jokes, Programming Puzzles, Programming Puzzles Overflow

query: p p
expected: Programming Puzzles, Programming Puzzles Overflow
actual: Programming Puzzles, Programming Puzzles Overflow

query: e p
expected: 
actual: 

query: p o o
expected: 
actual:
https://ideone.com/RJgj6p
language:
JavaScript (SMonkey 60.2.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!