Ooops
November 28, 2020, 11:14:03 AM

Author Topic: [bmx] Simple prefix tree by matibee [ 1+ years ago ]  (Read 527 times)

Offline BlitzBot

  • Jr. Member
  • **
  • Posts: 1
[bmx] Simple prefix tree by matibee [ 1+ years ago ]
« on: June 29, 2017, 12:28:41 AM »
Title : Simple prefix tree
Author : matibee
Posted : 1+ years ago

Description : This is a fairly naive implementation of a prefix tree..

<a href="http://en.wikipedia.org/wiki/Trie" target="_blank">http://en.wikipedia.org/wiki/Trie[/url]

It only works with lower case, basic ascii [a..z] strings.


Code :
Code: BlitzMax
  1. SuperStrict
  2.  
  3. Type wordTreeNode
  4.         Field move:Object[26]   ' pointers to the next node for each letter [a-z]
  5.         Field stop:Int[26]      ' denotes a word ending with at this node
  6.        
  7.         Method AddWord( word$ )
  8.                 Local ch:Int = word$[0] - 97
  9.                 If ( Len (word$ ) = 1 )
  10.                         stop[ ch ] = True
  11.                 Else
  12.                         If ( Not move[ ch ] )
  13.                                 move[ ch ] = New wordTreeNode
  14.                         End If
  15.                         wordTreeNode( move[ ch ] ).AddWord( Right( word$, Len( word$ ) - 1 ) )
  16.                 End If
  17.         End Method
  18.        
  19.         Method CheckWord:Int ( word$ )
  20.                 Local ch:Int = word$[0] - 97
  21.                 If ( Len ( word$ ) = 1 )
  22.                         Return stop[ ch ]
  23.                 Else If ( move[ ch ] )
  24.                         Return wordTreeNode( move[ ch ] ).CheckWord( Right( word$, Len( word$ ) - 1 ) )
  25.                 End If
  26.                 Return False
  27.         End Method
  28.        
  29. End Type
  30.  
  31. Type wordTree
  32.         Field base:wordTreeNode[26]
  33.        
  34.         Method AddWord( word$ )
  35.                 Assert( Len( word$ ) > 1 ) Else "Word too short ~q" + word$ + "~q"
  36.                 Local ch:Int = word$[0] - 97
  37.                 If ( Not base[ ch ] ) base[ ch ] = New wordTreeNode
  38.                 base[ ch ].AddWord( Right( word$, Len( word$ ) - 1 ) )
  39.         End Method      
  40.        
  41.         Method CheckWord:Int ( word$ )
  42.                 If ( Len( word$ ) < 2 ) Return False
  43.                 Local ch:Int = word$[0] - 97
  44.                 If ( base[ ch ] ) Return base[ ch ].CheckWord( Right( word$, Len( word$ ) - 1 ) )
  45.                 Return False
  46.         End Method
  47.        
  48. End Type
  49.  
  50. ' example usage..
  51. Local tree:wordTree = New wordTree
  52. tree.Addword( "this" )
  53. tree.Addword( "establishment" )
  54. tree.Addword( "produces" )
  55. tree.AddWord( "aardvark" )
  56. tree.AddWord( "meat" )
  57. tree.Addword( "establishments" )        ' creates only 1 new node in the tree
  58. tree.Addword( "establish" )             ' creates NO new nodes!
  59.  
  60. Print tree.CheckWord( "establishment" ) ' check succeeds
  61. Print tree.CheckWord( "aardvar" )               ' check fails
  62. Print tree.CheckWord( "aardvark" )      ' check succeeds


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal