Grammalecte  Hex Artifact Content

Artifact de8212efb30ddaefd381c492376c630535e473acf6c330bc7a76d9962d45b87c:


0000: 23 21 70 79 74 68 6f 6e 33 0a 0a 23 20 52 55 4c  #!python3..# RUL
0010: 45 20 47 52 41 50 48 20 42 55 49 4c 44 45 52 0a  E GRAPH BUILDER.
0020: 23 0a 23 20 62 79 20 4f 6c 69 76 69 65 72 20 52  #.# by Olivier R
0030: 2e 0a 23 20 4c 69 63 65 6e 73 65 3a 20 4d 50 4c  ..# License: MPL
0040: 20 32 0a 0a 0a 69 6d 70 6f 72 74 20 6a 73 6f 6e   2...import json
0050: 0a 69 6d 70 6f 72 74 20 74 69 6d 65 0a 69 6d 70  .import time.imp
0060: 6f 72 74 20 74 72 61 63 65 62 61 63 6b 0a 0a 66  ort traceback..f
0070: 72 6f 6d 20 67 72 61 70 68 73 70 65 6c 6c 2e 70  rom graphspell.p
0080: 72 6f 67 72 65 73 73 62 61 72 20 69 6d 70 6f 72  rogressbar impor
0090: 74 20 50 72 6f 67 72 65 73 73 42 61 72 0a 0a 0a  t ProgressBar...
00a0: 0a 63 6c 61 73 73 20 44 41 54 47 3a 0a 20 20 20  .class DATG:.   
00b0: 20 22 22 22 44 49 52 45 43 54 20 41 43 59 43 4c   """DIRECT ACYCL
00c0: 49 43 20 54 4f 4b 45 4e 20 47 52 41 50 48 22 22  IC TOKEN GRAPH""
00d0: 22 0a 20 20 20 20 23 20 54 68 69 73 20 63 6f 64  ".    # This cod
00e0: 65 20 69 73 20 69 6e 73 70 69 72 65 64 20 66 72  e is inspired fr
00f0: 6f 6d 20 53 74 65 76 65 20 48 61 6e 6f 76 e2 80  om Steve Hanov..
0100: 99 73 20 44 41 57 47 2c 20 32 30 31 31 2e 20 28  .s DAWG, 2011. (
0110: 68 74 74 70 3a 2f 2f 73 74 65 76 65 68 61 6e 6f  http://stevehano
0120: 76 2e 63 61 2f 62 6c 6f 67 2f 69 6e 64 65 78 2e  v.ca/blog/index.
0130: 70 68 70 3f 69 64 3d 31 31 35 29 0a 0a 20 20 20  php?id=115)..   
0140: 20 64 65 66 20 5f 5f 69 6e 69 74 5f 5f 20 28 73   def __init__ (s
0150: 65 6c 66 2c 20 6c 52 75 6c 65 2c 20 73 4c 61 6e  elf, lRule, sLan
0160: 67 43 6f 64 65 29 3a 0a 20 20 20 20 20 20 20 20  gCode):.        
0170: 70 72 69 6e 74 28 22 3d 3d 3d 3d 3d 20 44 69 72  print("===== Dir
0180: 65 63 74 20 41 63 79 63 6c 69 63 20 54 6f 6b 65  ect Acyclic Toke
0190: 6e 20 47 72 61 70 68 20 2d 20 4d 69 6e 69 6d 61  n Graph - Minima
01a0: 6c 20 41 63 79 63 6c 69 63 20 46 69 6e 69 74 65  l Acyclic Finite
01b0: 20 53 74 61 74 65 20 41 75 74 6f 6d 61 74 6f 6e   State Automaton
01c0: 20 3d 3d 3d 3d 3d 22 29 0a 0a 20 20 20 20 20 20   =====")..      
01d0: 20 20 23 20 50 72 65 70 61 72 69 6e 67 20 44 41    # Preparing DA
01e0: 54 47 0a 20 20 20 20 20 20 20 20 70 72 69 6e 74  TG.        print
01f0: 28 22 20 3e 20 50 72 65 70 61 72 69 6e 67 20 6c  (" > Preparing l
0200: 69 73 74 20 6f 66 20 74 6f 6b 65 6e 73 22 29 0a  ist of tokens").
0210: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 73 4c 61          self.sLa
0220: 6e 67 43 6f 64 65 20 3d 20 73 4c 61 6e 67 43 6f  ngCode = sLangCo
0230: 64 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  de.        self.
0240: 6e 52 75 6c 65 20 3d 20 6c 65 6e 28 6c 52 75 6c  nRule = len(lRul
0250: 65 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  e).        self.
0260: 61 50 72 65 76 69 6f 75 73 52 75 6c 65 20 3d 20  aPreviousRule = 
0270: 5b 5d 0a 20 20 20 20 20 20 20 20 4e 6f 64 65 2e  [].        Node.
0280: 72 65 73 65 74 4e 65 78 74 49 64 28 29 0a 20 20  resetNextId().  
0290: 20 20 20 20 20 20 73 65 6c 66 2e 6f 52 6f 6f 74        self.oRoot
02a0: 20 3d 20 4e 6f 64 65 28 29 0a 20 20 20 20 20 20   = Node().      
02b0: 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65    self.lUnchecke
02c0: 64 4e 6f 64 65 73 20 3d 20 5b 5d 20 20 23 20 6c  dNodes = []  # l
02d0: 69 73 74 20 6f 66 20 6e 6f 64 65 73 20 74 68 61  ist of nodes tha
02e0: 74 20 68 61 76 65 20 6e 6f 74 20 62 65 65 6e 20  t have not been 
02f0: 63 68 65 63 6b 65 64 20 66 6f 72 20 64 75 70 6c  checked for dupl
0300: 69 63 61 74 69 6f 6e 2e 0a 20 20 20 20 20 20 20  ication..       
0310: 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65 64   self.lMinimized
0320: 4e 6f 64 65 73 20 3d 20 7b 7d 20 20 23 20 6c 69  Nodes = {}  # li
0330: 73 74 20 6f 66 20 75 6e 69 71 75 65 20 6e 6f 64  st of unique nod
0340: 65 73 20 74 68 61 74 20 68 61 76 65 20 62 65 65  es that have bee
0350: 6e 20 63 68 65 63 6b 65 64 20 66 6f 72 20 64 75  n checked for du
0360: 70 6c 69 63 61 74 69 6f 6e 2e 0a 20 20 20 20 20  plication..     
0370: 20 20 20 73 65 6c 66 2e 6e 4e 6f 64 65 20 3d 20     self.nNode = 
0380: 30 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e  0.        self.n
0390: 41 72 63 20 3d 20 30 0a 20 20 20 20 20 20 20 20  Arc = 0.        
03a0: 0a 20 20 20 20 20 20 20 20 23 20 62 75 69 6c 64  .        # build
03b0: 0a 20 20 20 20 20 20 20 20 6c 52 75 6c 65 2e 73  .        lRule.s
03c0: 6f 72 74 28 29 0a 20 20 20 20 20 20 20 20 6f 50  ort().        oP
03d0: 72 6f 67 42 61 72 20 3d 20 50 72 6f 67 72 65 73  rogBar = Progres
03e0: 73 42 61 72 28 30 2c 20 6c 65 6e 28 6c 52 75 6c  sBar(0, len(lRul
03f0: 65 29 29 0a 20 20 20 20 20 20 20 20 66 6f 72 20  e)).        for 
0400: 61 52 75 6c 65 20 69 6e 20 6c 52 75 6c 65 3a 0a  aRule in lRule:.
0410: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
0420: 2e 69 6e 73 65 72 74 28 61 52 75 6c 65 29 0a 20  .insert(aRule). 
0430: 20 20 20 20 20 20 20 20 20 20 20 6f 50 72 6f 67             oProg
0440: 42 61 72 2e 69 6e 63 72 65 6d 65 6e 74 28 31 29  Bar.increment(1)
0450: 0a 20 20 20 20 20 20 20 20 6f 50 72 6f 67 42 61  .        oProgBa
0460: 72 2e 64 6f 6e 65 28 29 0a 20 20 20 20 20 20 20  r.done().       
0470: 20 73 65 6c 66 2e 66 69 6e 69 73 68 28 29 0a 20   self.finish(). 
0480: 20 20 20 20 20 20 20 73 65 6c 66 2e 63 6f 75 6e         self.coun
0490: 74 4e 6f 64 65 73 28 29 0a 20 20 20 20 20 20 20  tNodes().       
04a0: 20 73 65 6c 66 2e 63 6f 75 6e 74 41 72 63 73 28   self.countArcs(
04b0: 29 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 64  ).        self.d
04c0: 69 73 70 6c 61 79 49 6e 66 6f 28 29 0a 0a 20 20  isplayInfo()..  
04d0: 20 20 23 20 42 55 49 4c 44 20 44 41 54 47 0a 20    # BUILD DATG. 
04e0: 20 20 20 64 65 66 20 69 6e 73 65 72 74 20 28 73     def insert (s
04f0: 65 6c 66 2c 20 61 52 75 6c 65 29 3a 0a 20 20 20  elf, aRule):.   
0500: 20 20 20 20 20 69 66 20 61 52 75 6c 65 20 3c 20       if aRule < 
0510: 73 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75  self.aPreviousRu
0520: 6c 65 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  le:.            
0530: 73 79 73 2e 65 78 69 74 28 22 23 20 45 72 72 6f  sys.exit("# Erro
0540: 72 3a 20 74 6f 6b 65 6e 73 20 6d 75 73 74 20 62  r: tokens must b
0550: 65 20 69 6e 73 65 72 74 65 64 20 69 6e 20 6f 72  e inserted in or
0560: 64 65 72 2e 22 29 0a 20 20 20 20 0a 20 20 20 20  der.").    .    
0570: 20 20 20 20 23 20 66 69 6e 64 20 63 6f 6d 6d 6f      # find commo
0580: 6e 20 70 72 65 66 69 78 20 62 65 74 77 65 65 6e  n prefix between
0590: 20 77 6f 72 64 20 61 6e 64 20 70 72 65 76 69 6f   word and previo
05a0: 75 73 20 77 6f 72 64 0a 20 20 20 20 20 20 20 20  us word.        
05b0: 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 20 3d 20  nCommonPrefix = 
05c0: 30 0a 20 20 20 20 20 20 20 20 66 6f 72 20 69 20  0.        for i 
05d0: 69 6e 20 72 61 6e 67 65 28 6d 69 6e 28 6c 65 6e  in range(min(len
05e0: 28 61 52 75 6c 65 29 2c 20 6c 65 6e 28 73 65 6c  (aRule), len(sel
05f0: 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c 65 29  f.aPreviousRule)
0600: 29 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  )):.            
0610: 69 66 20 61 52 75 6c 65 5b 69 5d 20 21 3d 20 73  if aRule[i] != s
0620: 65 6c 66 2e 61 50 72 65 76 69 6f 75 73 52 75 6c  elf.aPreviousRul
0630: 65 5b 69 5d 3a 0a 20 20 20 20 20 20 20 20 20 20  e[i]:.          
0640: 20 20 20 20 20 20 62 72 65 61 6b 0a 20 20 20 20        break.    
0650: 20 20 20 20 20 20 20 20 6e 43 6f 6d 6d 6f 6e 50          nCommonP
0660: 72 65 66 69 78 20 2b 3d 20 31 0a 0a 20 20 20 20  refix += 1..    
0670: 20 20 20 20 23 20 43 68 65 63 6b 20 74 68 65 20      # Check the 
0680: 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73 20  lUncheckedNodes 
0690: 66 6f 72 20 72 65 64 75 6e 64 61 6e 74 20 6e 6f  for redundant no
06a0: 64 65 73 2c 20 70 72 6f 63 65 65 64 69 6e 67 20  des, proceeding 
06b0: 66 72 6f 6d 20 6c 61 73 74 0a 20 20 20 20 20 20  from last.      
06c0: 20 20 23 20 6f 6e 65 20 64 6f 77 6e 20 74 6f 20    # one down to 
06d0: 74 68 65 20 63 6f 6d 6d 6f 6e 20 70 72 65 66 69  the common prefi
06e0: 78 20 73 69 7a 65 2e 20 54 68 65 6e 20 74 72 75  x size. Then tru
06f0: 6e 63 61 74 65 20 74 68 65 20 6c 69 73 74 20 61  ncate the list a
0700: 74 20 74 68 61 74 20 70 6f 69 6e 74 2e 0a 20 20  t that point..  
0710: 20 20 20 20 20 20 73 65 6c 66 2e 5f 6d 69 6e 69        self._mini
0720: 6d 69 7a 65 28 6e 43 6f 6d 6d 6f 6e 50 72 65 66  mize(nCommonPref
0730: 69 78 29 0a 0a 20 20 20 20 20 20 20 20 23 20 61  ix)..        # a
0740: 64 64 20 74 68 65 20 73 75 66 66 69 78 2c 20 73  dd the suffix, s
0750: 74 61 72 74 69 6e 67 20 66 72 6f 6d 20 74 68 65  tarting from the
0760: 20 63 6f 72 72 65 63 74 20 6e 6f 64 65 20 6d 69   correct node mi
0770: 64 2d 77 61 79 20 74 68 72 6f 75 67 68 20 74 68  d-way through th
0780: 65 20 67 72 61 70 68 0a 20 20 20 20 20 20 20 20  e graph.        
0790: 69 66 20 6c 65 6e 28 73 65 6c 66 2e 6c 55 6e 63  if len(self.lUnc
07a0: 68 65 63 6b 65 64 4e 6f 64 65 73 29 20 3d 3d 20  heckedNodes) == 
07b0: 30 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 6f  0:.            o
07c0: 4e 6f 64 65 20 3d 20 73 65 6c 66 2e 6f 52 6f 6f  Node = self.oRoo
07d0: 74 0a 20 20 20 20 20 20 20 20 65 6c 73 65 3a 0a  t.        else:.
07e0: 20 20 20 20 20 20 20 20 20 20 20 20 6f 4e 6f 64              oNod
07f0: 65 20 3d 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63  e = self.lUnchec
0800: 6b 65 64 4e 6f 64 65 73 5b 2d 31 5d 5b 32 5d 0a  kedNodes[-1][2].
0810: 0a 20 20 20 20 20 20 20 20 69 54 6f 6b 65 6e 20  .        iToken 
0820: 3d 20 6e 43 6f 6d 6d 6f 6e 50 72 65 66 69 78 0a  = nCommonPrefix.
0830: 20 20 20 20 20 20 20 20 66 6f 72 20 74 6f 6b 65          for toke
0840: 6e 20 69 6e 20 61 52 75 6c 65 5b 6e 43 6f 6d 6d  n in aRule[nComm
0850: 6f 6e 50 72 65 66 69 78 3a 5d 3a 0a 20 20 20 20  onPrefix:]:.    
0860: 20 20 20 20 20 20 20 20 6f 4e 65 78 74 4e 6f 64          oNextNod
0870: 65 20 3d 20 4e 6f 64 65 28 29 0a 20 20 20 20 20  e = Node().     
0880: 20 20 20 20 20 20 20 6f 4e 6f 64 65 2e 64 41 72         oNode.dAr
0890: 63 73 5b 74 6f 6b 65 6e 5d 20 3d 20 6f 4e 65 78  cs[token] = oNex
08a0: 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20 20 20  tNode.          
08b0: 20 20 73 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65    self.lUnchecke
08c0: 64 4e 6f 64 65 73 2e 61 70 70 65 6e 64 28 28 6f  dNodes.append((o
08d0: 4e 6f 64 65 2c 20 74 6f 6b 65 6e 2c 20 6f 4e 65  Node, token, oNe
08e0: 78 74 4e 6f 64 65 29 29 0a 20 20 20 20 20 20 20  xtNode)).       
08f0: 20 20 20 20 20 69 66 20 69 54 6f 6b 65 6e 20 3d       if iToken =
0900: 3d 20 28 6c 65 6e 28 61 52 75 6c 65 29 20 2d 20  = (len(aRule) - 
0910: 34 29 3a 20 0a 20 20 20 20 20 20 20 20 20 20 20  4): .           
0920: 20 20 20 20 20 6f 4e 6f 64 65 2e 62 46 69 6e 61       oNode.bFina
0930: 6c 20 3d 20 54 72 75 65 0a 20 20 20 20 20 20 20  l = True.       
0940: 20 20 20 20 20 20 20 20 20 6f 4e 65 78 74 4e 6f           oNextNo
0950: 64 65 2e 62 49 6e 66 6f 20 3d 20 54 72 75 65 0a  de.bInfo = True.
0960: 20 20 20 20 20 20 20 20 20 20 20 20 69 54 6f 6b              iTok
0970: 65 6e 20 2b 3d 20 31 0a 20 20 20 20 20 20 20 20  en += 1.        
0980: 20 20 20 20 6f 4e 6f 64 65 20 3d 20 6f 4e 65 78      oNode = oNex
0990: 74 4e 6f 64 65 0a 20 20 20 20 20 20 20 20 6f 4e  tNode.        oN
09a0: 6f 64 65 2e 62 46 69 6e 61 6c 20 3d 20 54 72 75  ode.bFinal = Tru
09b0: 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 61  e.        self.a
09c0: 50 72 65 76 69 6f 75 73 52 75 6c 65 20 3d 20 61  PreviousRule = a
09d0: 52 75 6c 65 0a 0a 20 20 20 20 64 65 66 20 66 69  Rule..    def fi
09e0: 6e 69 73 68 20 28 73 65 6c 66 29 3a 0a 20 20 20  nish (self):.   
09f0: 20 20 20 20 20 22 6d 69 6e 69 6d 69 7a 65 20 75       "minimize u
0a00: 6e 63 68 65 63 6b 65 64 20 6e 6f 64 65 73 22 0a  nchecked nodes".
0a10: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 5f 6d 69          self._mi
0a20: 6e 69 6d 69 7a 65 28 30 29 0a 0a 20 20 20 20 64  nimize(0)..    d
0a30: 65 66 20 5f 6d 69 6e 69 6d 69 7a 65 20 28 73 65  ef _minimize (se
0a40: 6c 66 2c 20 64 6f 77 6e 54 6f 29 3a 0a 20 20 20  lf, downTo):.   
0a50: 20 20 20 20 20 23 20 70 72 6f 63 65 65 64 20 66       # proceed f
0a60: 72 6f 6d 20 74 68 65 20 6c 65 61 66 20 75 70 20  rom the leaf up 
0a70: 74 6f 20 61 20 63 65 72 74 61 69 6e 20 70 6f 69  to a certain poi
0a80: 6e 74 0a 20 20 20 20 20 20 20 20 66 6f 72 20 69  nt.        for i
0a90: 20 69 6e 20 72 61 6e 67 65 28 20 6c 65 6e 28 73   in range( len(s
0aa0: 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f  elf.lUncheckedNo
0ab0: 64 65 73 29 2d 31 2c 20 64 6f 77 6e 54 6f 2d 31  des)-1, downTo-1
0ac0: 2c 20 2d 31 20 29 3a 0a 20 20 20 20 20 20 20 20  , -1 ):.        
0ad0: 20 20 20 20 6f 4e 6f 64 65 2c 20 74 6f 6b 65 6e      oNode, token
0ae0: 2c 20 6f 43 68 69 6c 64 4e 6f 64 65 20 3d 20 73  , oChildNode = s
0af0: 65 6c 66 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f  elf.lUncheckedNo
0b00: 64 65 73 5b 69 5d 0a 20 20 20 20 20 20 20 20 20  des[i].         
0b10: 20 20 20 69 66 20 6f 43 68 69 6c 64 4e 6f 64 65     if oChildNode
0b20: 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69   in self.lMinimi
0b30: 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20 20 20  zedNodes:.      
0b40: 20 20 20 20 20 20 20 20 20 20 23 20 72 65 70 6c            # repl
0b50: 61 63 65 20 74 68 65 20 63 68 69 6c 64 20 77 69  ace the child wi
0b60: 74 68 20 74 68 65 20 70 72 65 76 69 6f 75 73 6c  th the previousl
0b70: 79 20 65 6e 63 6f 75 6e 74 65 72 65 64 20 6f 6e  y encountered on
0b80: 65 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  e.              
0b90: 20 20 6f 4e 6f 64 65 2e 64 41 72 63 73 5b 74 6f    oNode.dArcs[to
0ba0: 6b 65 6e 5d 20 3d 20 73 65 6c 66 2e 6c 4d 69 6e  ken] = self.lMin
0bb0: 69 6d 69 7a 65 64 4e 6f 64 65 73 5b 6f 43 68 69  imizedNodes[oChi
0bc0: 6c 64 4e 6f 64 65 5d 0a 20 20 20 20 20 20 20 20  ldNode].        
0bd0: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
0be0: 20 20 20 20 20 20 20 20 20 20 23 20 61 64 64 20            # add 
0bf0: 74 68 65 20 73 74 61 74 65 20 74 6f 20 74 68 65  the state to the
0c00: 20 6d 69 6e 69 6d 69 7a 65 64 20 6e 6f 64 65 73   minimized nodes
0c10: 2e 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ..              
0c20: 20 20 73 65 6c 66 2e 6c 4d 69 6e 69 6d 69 7a 65    self.lMinimize
0c30: 64 4e 6f 64 65 73 5b 6f 43 68 69 6c 64 4e 6f 64  dNodes[oChildNod
0c40: 65 5d 20 3d 20 6f 43 68 69 6c 64 4e 6f 64 65 0a  e] = oChildNode.
0c50: 20 20 20 20 20 20 20 20 20 20 20 20 73 65 6c 66              self
0c60: 2e 6c 55 6e 63 68 65 63 6b 65 64 4e 6f 64 65 73  .lUncheckedNodes
0c70: 2e 70 6f 70 28 29 0a 0a 20 20 20 20 64 65 66 20  .pop()..    def 
0c80: 63 6f 75 6e 74 4e 6f 64 65 73 20 28 73 65 6c 66  countNodes (self
0c90: 29 3a 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e  ):.        self.
0ca0: 6e 4e 6f 64 65 20 3d 20 6c 65 6e 28 73 65 6c 66  nNode = len(self
0cb0: 2e 6c 4d 69 6e 69 6d 69 7a 65 64 4e 6f 64 65 73  .lMinimizedNodes
0cc0: 29 0a 0a 20 20 20 20 64 65 66 20 63 6f 75 6e 74  )..    def count
0cd0: 41 72 63 73 20 28 73 65 6c 66 29 3a 0a 20 20 20  Arcs (self):.   
0ce0: 20 20 20 20 20 73 65 6c 66 2e 6e 41 72 63 20 3d       self.nArc =
0cf0: 20 30 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6f   0.        for o
0d00: 4e 6f 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69  Node in self.lMi
0d10: 6e 69 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20  nimizedNodes:.  
0d20: 20 20 20 20 20 20 20 20 20 20 73 65 6c 66 2e 6e            self.n
0d30: 41 72 63 20 2b 3d 20 6c 65 6e 28 6f 4e 6f 64 65  Arc += len(oNode
0d40: 2e 64 41 72 63 73 29 0a 20 20 20 20 20 20 20 20  .dArcs).        
0d50: 0a 20 20 20 20 64 65 66 20 6c 6f 6f 6b 75 70 20  .    def lookup 
0d60: 28 73 65 6c 66 2c 20 73 57 6f 72 64 29 3a 0a 20  (self, sWord):. 
0d70: 20 20 20 20 20 20 20 6f 4e 6f 64 65 20 3d 20 73         oNode = s
0d80: 65 6c 66 2e 6f 52 6f 6f 74 0a 20 20 20 20 20 20  elf.oRoot.      
0d90: 20 20 66 6f 72 20 63 20 69 6e 20 73 57 6f 72 64    for c in sWord
0da0: 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20 69 66  :.            if
0db0: 20 63 20 6e 6f 74 20 69 6e 20 6f 4e 6f 64 65 2e   c not in oNode.
0dc0: 64 41 72 63 73 3a 0a 20 20 20 20 20 20 20 20 20  dArcs:.         
0dd0: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 46 61         return Fa
0de0: 6c 73 65 0a 20 20 20 20 20 20 20 20 20 20 20 20  lse.            
0df0: 6f 4e 6f 64 65 20 3d 20 6f 4e 6f 64 65 2e 64 41  oNode = oNode.dA
0e00: 72 63 73 5b 63 5d 0a 20 20 20 20 20 20 20 20 72  rcs[c].        r
0e10: 65 74 75 72 6e 20 6f 4e 6f 64 65 2e 62 46 69 6e  eturn oNode.bFin
0e20: 61 6c 0a 0a 20 20 20 20 64 65 66 20 64 69 73 70  al..    def disp
0e30: 6c 61 79 49 6e 66 6f 20 28 73 65 6c 66 29 3a 0a  layInfo (self):.
0e40: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 20          print(" 
0e50: 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c 7d  * {:<12} {:>16,}
0e60: 22 2e 66 6f 72 6d 61 74 28 22 52 75 6c 65 73 3a  ".format("Rules:
0e70: 22 2c 20 73 65 6c 66 2e 6e 52 75 6c 65 29 29 0a  ", self.nRule)).
0e80: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 20          print(" 
0e90: 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c 7d  * {:<12} {:>16,}
0ea0: 22 2e 66 6f 72 6d 61 74 28 22 4e 6f 64 65 73 3a  ".format("Nodes:
0eb0: 22 2c 20 73 65 6c 66 2e 6e 4e 6f 64 65 29 29 0a  ", self.nNode)).
0ec0: 20 20 20 20 20 20 20 20 70 72 69 6e 74 28 22 20          print(" 
0ed0: 2a 20 7b 3a 3c 31 32 7d 20 7b 3a 3e 31 36 2c 7d  * {:<12} {:>16,}
0ee0: 22 2e 66 6f 72 6d 61 74 28 22 41 72 63 73 3a 22  ".format("Arcs:"
0ef0: 2c 20 73 65 6c 66 2e 6e 41 72 63 29 29 0a 0a 20  , self.nArc)).. 
0f00: 20 20 20 64 65 66 20 63 72 65 61 74 65 47 72 61     def createGra
0f10: 70 68 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  ph (self):.     
0f20: 20 20 20 64 47 72 61 70 68 20 3d 20 7b 20 30 3a     dGraph = { 0:
0f30: 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e 67 65 74 4e   self.oRoot.getN
0f40: 6f 64 65 41 73 44 69 63 74 28 29 20 7d 0a 20 20  odeAsDict() }.  
0f50: 20 20 20 20 20 20 70 72 69 6e 74 28 30 2c 20 22        print(0, "
0f60: 5c 74 22 2c 20 73 65 6c 66 2e 6f 52 6f 6f 74 2e  \t", self.oRoot.
0f70: 67 65 74 4e 6f 64 65 41 73 44 69 63 74 28 29 29  getNodeAsDict())
0f80: 0a 20 20 20 20 20 20 20 20 66 6f 72 20 6f 4e 6f  .        for oNo
0f90: 64 65 20 69 6e 20 73 65 6c 66 2e 6c 4d 69 6e 69  de in self.lMini
0fa0: 6d 69 7a 65 64 4e 6f 64 65 73 3a 0a 20 20 20 20  mizedNodes:.    
0fb0: 20 20 20 20 20 20 20 20 73 48 61 73 68 49 64 20          sHashId 
0fc0: 3d 20 6f 4e 6f 64 65 2e 5f 5f 68 61 73 68 5f 5f  = oNode.__hash__
0fd0: 28 29 20 0a 20 20 20 20 20 20 20 20 20 20 20 20  () .            
0fe0: 69 66 20 73 48 61 73 68 49 64 20 6e 6f 74 20 69  if sHashId not i
0ff0: 6e 20 64 47 72 61 70 68 3a 0a 20 20 20 20 20 20  n dGraph:.      
1000: 20 20 20 20 20 20 20 20 20 20 64 47 72 61 70 68            dGraph
1010: 5b 73 48 61 73 68 49 64 5d 20 3d 20 6f 4e 6f 64  [sHashId] = oNod
1020: 65 2e 67 65 74 4e 6f 64 65 41 73 44 69 63 74 28  e.getNodeAsDict(
1030: 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20  ).              
1040: 20 20 70 72 69 6e 74 28 73 48 61 73 68 49 64 2c    print(sHashId,
1050: 20 22 5c 74 22 2c 20 64 47 72 61 70 68 5b 73 48   "\t", dGraph[sH
1060: 61 73 68 49 64 5d 29 0a 20 20 20 20 20 20 20 20  ashId]).        
1070: 20 20 20 20 65 6c 73 65 3a 0a 20 20 20 20 20 20      else:.      
1080: 20 20 20 20 20 20 20 20 20 20 70 72 69 6e 74 28            print(
1090: 22 45 72 72 6f 72 2e 20 44 6f 75 62 6c 65 20 6e  "Error. Double n
10a0: 6f 64 65 e2 80 a6 20 73 61 6d 65 20 69 64 3a 20  ode... same id: 
10b0: 22 2c 20 73 48 61 73 68 49 64 29 0a 20 20 20 20  ", sHashId).    
10c0: 20 20 20 20 20 20 20 20 20 20 20 20 70 72 69 6e              prin
10d0: 74 28 73 74 72 28 6f 4e 6f 64 65 2e 67 65 74 4e  t(str(oNode.getN
10e0: 6f 64 65 41 73 44 69 63 74 28 29 29 29 0a 20 20  odeAsDict())).  
10f0: 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 47 72        return dGr
1100: 61 70 68 0a 0a 0a 0a 63 6c 61 73 73 20 4e 6f 64  aph....class Nod
1110: 65 3a 0a 20 20 20 20 4e 65 78 74 49 64 20 3d 20  e:.    NextId = 
1120: 30 0a 20 20 20 20 0a 20 20 20 20 64 65 66 20 5f  0.    .    def _
1130: 5f 69 6e 69 74 5f 5f 20 28 73 65 6c 66 29 3a 0a  _init__ (self):.
1140: 20 20 20 20 20 20 20 20 73 65 6c 66 2e 69 20 3d          self.i =
1150: 20 4e 6f 64 65 2e 4e 65 78 74 49 64 0a 20 20 20   Node.NextId.   
1160: 20 20 20 20 20 4e 6f 64 65 2e 4e 65 78 74 49 64       Node.NextId
1170: 20 2b 3d 20 31 0a 20 20 20 20 20 20 20 20 73 65   += 1.        se
1180: 6c 66 2e 62 46 69 6e 61 6c 20 3d 20 46 61 6c 73  lf.bFinal = Fals
1190: 65 0a 20 20 20 20 20 20 20 20 73 65 6c 66 2e 62  e.        self.b
11a0: 49 6e 66 6f 20 3d 20 46 61 6c 73 65 0a 20 20 20  Info = False.   
11b0: 20 20 20 20 20 73 65 6c 66 2e 64 41 72 63 73 20       self.dArcs 
11c0: 3d 20 7b 7d 20 20 20 20 20 20 20 20 20 20 23 20  = {}          # 
11d0: 6b 65 79 3a 20 61 72 63 20 76 61 6c 75 65 3b 20  key: arc value; 
11e0: 76 61 6c 75 65 3a 20 61 20 6e 6f 64 65 0a 0a 20  value: a node.. 
11f0: 20 20 20 40 63 6c 61 73 73 6d 65 74 68 6f 64 0a     @classmethod.
1200: 20 20 20 20 64 65 66 20 72 65 73 65 74 4e 65 78      def resetNex
1210: 74 49 64 20 28 63 6c 73 29 3a 0a 20 20 20 20 20  tId (cls):.     
1220: 20 20 20 63 6c 73 2e 4e 65 78 74 49 64 20 3d 20     cls.NextId = 
1230: 30 0a 0a 20 20 20 20 64 65 66 20 5f 5f 73 74 72  0..    def __str
1240: 5f 5f 20 28 73 65 6c 66 29 3a 0a 20 20 20 20 20  __ (self):.     
1250: 20 20 20 23 20 43 61 75 74 69 6f 6e 21 20 74 68     # Caution! th
1260: 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 75  is function is u
1270: 73 65 64 20 66 6f 72 20 68 61 73 68 69 6e 67 20  sed for hashing 
1280: 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 21 0a  and comparison!.
1290: 20 20 20 20 20 20 20 20 63 46 69 6e 61 6c 20 3d          cFinal =
12a0: 20 22 31 22 20 20 69 66 20 73 65 6c 66 2e 62 46   "1"  if self.bF
12b0: 69 6e 61 6c 20 20 65 6c 73 65 20 22 30 22 0a 20  inal  else "0". 
12c0: 20 20 20 20 20 20 20 63 49 6e 66 6f 20 3d 20 22         cInfo = "
12d0: 31 22 20 20 69 66 20 73 65 6c 66 2e 62 49 6e 66  1"  if self.bInf
12e0: 6f 20 20 65 6c 73 65 20 22 30 22 0a 20 20 20 20  o  else "0".    
12f0: 20 20 20 20 6c 20 3d 20 5b 63 46 69 6e 61 6c 2c      l = [cFinal,
1300: 20 63 49 6e 66 6f 5d 0a 20 20 20 20 20 20 20 20   cInfo].        
1310: 66 6f 72 20 28 6b 65 79 2c 20 6f 4e 6f 64 65 29  for (key, oNode)
1320: 20 69 6e 20 73 65 6c 66 2e 64 41 72 63 73 2e 69   in self.dArcs.i
1330: 74 65 6d 73 28 29 3a 0a 20 20 20 20 20 20 20 20  tems():.        
1340: 20 20 20 20 6c 2e 61 70 70 65 6e 64 28 73 74 72      l.append(str
1350: 28 6b 65 79 29 29 0a 20 20 20 20 20 20 20 20 20  (key)).         
1360: 20 20 20 6c 2e 61 70 70 65 6e 64 28 73 74 72 28     l.append(str(
1370: 6f 4e 6f 64 65 2e 69 29 29 0a 20 20 20 20 20 20  oNode.i)).      
1380: 20 20 72 65 74 75 72 6e 20 22 5f 22 2e 6a 6f 69    return "_".joi
1390: 6e 28 6c 29 0a 0a 20 20 20 20 64 65 66 20 5f 5f  n(l)..    def __
13a0: 68 61 73 68 5f 5f 20 28 73 65 6c 66 29 3a 0a 20  hash__ (self):. 
13b0: 20 20 20 20 20 20 20 23 20 55 73 65 64 20 61 73         # Used as
13c0: 20 61 20 6b 65 79 20 69 6e 20 61 20 70 79 74 68   a key in a pyth
13d0: 6f 6e 20 64 69 63 74 69 6f 6e 61 72 79 2e 0a 20  on dictionary.. 
13e0: 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 73 65         return se
13f0: 6c 66 2e 5f 5f 73 74 72 5f 5f 28 29 2e 5f 5f 68  lf.__str__().__h
1400: 61 73 68 5f 5f 28 29 0a 0a 20 20 20 20 64 65 66  ash__()..    def
1410: 20 5f 5f 65 71 5f 5f 20 28 73 65 6c 66 2c 20 6f   __eq__ (self, o
1420: 74 68 65 72 29 3a 0a 20 20 20 20 20 20 20 20 23  ther):.        #
1430: 20 55 73 65 64 20 61 73 20 61 20 6b 65 79 20 69   Used as a key i
1440: 6e 20 61 20 70 79 74 68 6f 6e 20 64 69 63 74 69  n a python dicti
1450: 6f 6e 61 72 79 2e 0a 20 20 20 20 20 20 20 20 23  onary..        #
1460: 20 4e 6f 64 65 73 20 61 72 65 20 65 71 75 69 76   Nodes are equiv
1470: 61 6c 65 6e 74 20 69 66 20 74 68 65 79 20 68 61  alent if they ha
1480: 76 65 20 69 64 65 6e 74 69 63 61 6c 20 61 72 63  ve identical arc
1490: 73 2c 20 61 6e 64 20 65 61 63 68 20 69 64 65 6e  s, and each iden
14a0: 74 69 63 61 6c 20 61 72 63 20 6c 65 61 64 73 20  tical arc leads 
14b0: 74 6f 20 69 64 65 6e 74 69 63 61 6c 20 73 74 61  to identical sta
14c0: 74 65 73 2e 0a 20 20 20 20 20 20 20 20 72 65 74  tes..        ret
14d0: 75 72 6e 20 73 65 6c 66 2e 5f 5f 73 74 72 5f 5f  urn self.__str__
14e0: 28 29 20 3d 3d 20 6f 74 68 65 72 2e 5f 5f 73 74  () == other.__st
14f0: 72 5f 5f 28 29 20 20 20 20 20 20 20 20 0a 0a 20  r__()        .. 
1500: 20 20 20 64 65 66 20 67 65 74 4e 6f 64 65 41 73     def getNodeAs
1510: 44 69 63 74 20 28 73 65 6c 66 29 3a 0a 20 20 20  Dict (self):.   
1520: 20 20 20 20 20 22 72 65 74 75 72 6e 73 20 74 68       "returns th
1530: 65 20 6e 6f 64 65 20 61 73 20 61 20 64 69 63 74  e node as a dict
1540: 69 6f 6e 61 72 79 20 73 74 72 75 63 74 75 72 65  ionary structure
1550: 22 0a 20 20 20 20 20 20 20 20 64 4e 6f 64 65 20  ".        dNode 
1560: 3d 20 7b 20 7d 0a 20 20 20 20 20 20 20 20 66 6f  = { }.        fo
1570: 72 20 61 72 63 2c 20 6f 4e 6f 64 65 20 69 6e 20  r arc, oNode in 
1580: 73 65 6c 66 2e 64 41 72 63 73 2e 69 74 65 6d 73  self.dArcs.items
1590: 28 29 3a 0a 20 20 20 20 20 20 20 20 20 20 20 20  ():.            
15a0: 64 4e 6f 64 65 5b 61 72 63 5d 20 3d 20 6f 4e 6f  dNode[arc] = oNo
15b0: 64 65 2e 5f 5f 68 61 73 68 5f 5f 28 29 0a 20 20  de.__hash__().  
15c0: 20 20 20 20 20 20 69 66 20 73 65 6c 66 2e 62 46        if self.bF
15d0: 69 6e 61 6c 3a 0a 20 20 20 20 20 20 20 20 20 20  inal:.          
15e0: 20 20 64 4e 6f 64 65 5b 22 3c 66 69 6e 61 6c 3e    dNode["<final>
15f0: 22 5d 20 3d 20 22 22 0a 20 20 20 20 20 20 20 20  "] = "".        
1600: 69 66 20 73 65 6c 66 2e 62 49 6e 66 6f 3a 0a 20  if self.bInfo:. 
1610: 20 20 20 20 20 20 20 20 20 20 20 64 4e 6f 64 65             dNode
1620: 5b 22 3c 69 6e 66 6f 3e 22 5d 20 3d 20 22 22 0a  ["<info>"] = "".
1630: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 64          return d
1640: 4e 6f 64 65 0a                                   Node.