Posted By

jatkins on 03/08/14


Tagged

data tree datastructure structure trie


Versions (?)

Random Access Trie


 / Published in: JavaScript
 

yep.

  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4. <meta http-equiv="content-type" content="text/html; charset=utf-8" />
  5. <title>Random Access Trie</title>
  6. <script type="text/javascript">
  7. //<![CDATA[
  8. // (c) 2014 Josh Atkins.
  9. // All rights reserved.
  10.  
  11. var randomAccessTrie = function() {
  12. this.data = {};
  13. this.wordNodes = {count: 0};
  14.  
  15. this.takeAWalk = function(substringToWalkToEndOf, curCharIndex, curNode) {
  16. substringToWalkToEndOf = substringToWalkToEndOf.toLowerCase();
  17.  
  18. if(typeof curCharIndex == 'undefined')
  19. var curCharIndex = 0;
  20.  
  21. var prevNode = curNode;
  22.  
  23. if(typeof curNode == 'undefined')
  24. var curNode = this.data[substringToWalkToEndOf.charAt(curCharIndex)];
  25. else
  26. curNode = curNode[substringToWalkToEndOf.charAt(curCharIndex)];
  27.  
  28. if(curNode)
  29. return this.takeAWalk(substringToWalkToEndOf, ++curCharIndex, curNode);
  30. else
  31. return prevNode;
  32. };
  33.  
  34. this.autoComplete = function(curNode, completedSoFar) {
  35. if(typeof curNode == 'undefined')
  36. var curNode = this.data;
  37.  
  38. if(typeof completedSoFar == 'undefined')
  39. var completedSoFar = '';
  40.  
  41. if(curNode) {
  42. if(typeof curNode['word'] != 'undefined')
  43. return curNode['word'];
  44. if(Object.keys(curNode)[0] == '_EOW')
  45. return curNode['_EOW'][0].word;
  46. else
  47. return this.autoComplete(curNode[Object.keys(curNode)[0]], completedSoFar + Object.keys(curNode)[0]);
  48. }
  49. };
  50.  
  51. this.aC = function(curNode, wordsSoFar) {
  52. if(typeof curNode == 'undefined')
  53. var curNode = this.data;
  54.  
  55. if(typeof wordsSoFar == 'undefined')
  56. var wordsSoFar = {};//[]
  57.  
  58. for(node in curNode) {
  59. if(!wordsSoFar[this.autoComplete(curNode[node])])
  60. wordsSoFar[this.autoComplete(curNode[node])] = true;
  61. //wordsSoFar.push(this.autoComplete(curNode[node]));
  62. }
  63.  
  64. return wordsSoFar;
  65. };
  66.  
  67. this.addWord = function(wordToAdd) { // this basically creates a suffix tree for the word and inserts it into the main trie
  68. wordToAdd = wordToAdd.toLowerCase();
  69.  
  70. if(!this.wordNodes[wordToAdd]) { // don't add duplicates
  71. var wordNode = {
  72. indexWhenAdded: parseInt(this.wordNodes.count),
  73. word: wordToAdd.toString()
  74. };
  75. this.wordNodes[wordToAdd] = wordNode;
  76. this.wordNodes.count++;
  77.  
  78. for(var wordPos = 0; wordPos < wordToAdd.length; wordPos++) {
  79. var curNode = this.data;
  80.  
  81. for(suffixPos = wordPos; suffixPos < wordToAdd.length; suffixPos++) {
  82. if(!curNode[wordToAdd.charAt(suffixPos)])
  83. curNode[wordToAdd.charAt(suffixPos)] = {};
  84.  
  85. curNode = curNode[wordToAdd.charAt(suffixPos)];
  86. }
  87.  
  88. if(!curNode['_EOW'])
  89. curNode['_EOW'] = [];
  90.  
  91. curNode['_EOW'].push(wordNode);
  92. }
  93. }
  94. };
  95. };
  96.  
  97. function test() {
  98. window.testRAT = new randomAccessTrie;
  99.  
  100. testRAT.addWord('Hello');
  101. testRAT.addWord('Hi Built');
  102. testRAT.addWord('his');
  103. testRAT.addWord('the quick brown fox jumps over the lazy dog');
  104. testRAT.addWord('George W. Bush');
  105. testRAT.addWord('George Clinton');
  106. testRAT.addWord('William Jefferson Clinton');
  107. testRAT.addWord('Thomas Jefferson');
  108. testRAT.addWord('Jefferson Davis');//(Dishonorable mention)
  109. //console.log(testRAT.takeAWalk('ui'));
  110.  
  111. console.log(testRAT.aC(testRAT.takeAWalk('C')));
  112. // the reason this is having problems is because it is only walking to one of the 'C's
  113. }
  114. //]]>
  115. </script>
  116. </head>
  117. <body onload="test();">
  118. </body>
  119. </html>

Report this snippet  

You need to login to post a comment.