Guest User

Untitled

a guest
Nov 17th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 11.43 KB | None | 0 0
  1. '''
  2. Trie: add, find, find all suffixes
  3. '''
  4.  
  5. #common finnish words
  6. vocab = ["AIKA","AINA","ALKAA","ANTAA","ASIA","EI","ENNEN","ENSIMMÄINEN","ERÄS","ERI","ESITTÄÄ","ETTÄ",
  7. "HÄN","HE","HYVÄ","HYVIN","IHMINEN","ITSE","JA","JÄÄDÄ","JÄLKEEN","JO","JOKA","JOKIN","JOS","JOUTUA","JUMALA",
  8. "KAIKKI","KAKSI","KANSSA","KATSOA","KÄYDÄ","KÄYTTÄÄ","KOKO","KOSKA","KUIN","KUITENKIN","KUN","KUULUA","KYSYMYS",
  9. "LAPSI","MAA","MAINITA","ME","MENNÄ","MIELI","MIES","MIKÄ","MINÄ","MONI","MUKAAN","MUTTA","MUU","MYÖS","NÄHDÄ","NÄIN","NÄMÄ",
  10. "NE","NIIN","NYT","OLLA","OMA","OSA","OTTAA","PÄIVÄ","PALJON","PIENI","PITÄÄ",
  11. "SAADA","SAATTAA","SAMA","SANOA","SE","SEKÄ","SELLAINEN","SIELLÄ","SINÄ","SITTEN","SUOMI","SUORITTAA","SUURI",
  12. "TAI","TÄMÄ","TAPA","TAPAHTUA","TÄSSÄ","TEHDÄ","TIETÄÄ","TOINEN","TULLA","TYÖ",
  13. "UUSI","VAAN","VAIKKA","VAIN","VIELÄ","VOIDA","VUOSI","YKSI",
  14.  
  15. "SILLÄ","VANHA","SILLOIN","TUNTEA","NUORI","LÄHTEÄ","PÄÄSTÄ","PUOLI","TARVITA","JUURI","KUVA","SIINÄ","ELÄMÄ","SANA","TÄLLAINEN","TE","TODETA",
  16. "KERTA","KUTEN","PUHUA","MÄÄRÄ","USEA","YLEINEN","AIVAN","TEHTÄVÄ","TAPAUS","LISÄKSI","MISSÄ","HUOMIO","NOIN","PITKÄ","TUO","SYY","TÄÄLLÄ",
  17. "MIKÄÄN","POIKA","KOLME","KYLLÄ","TÄRKEÄ","JOKAINEN","KERTOA","KOHTA","MAHDOLLINEN","TULOS","MAAILMA","TIE","MITÄ","HALUTA","KOSKEA","YHTEYS",
  18. "MITEN","VESI","ALUE","USEIN","YLEENSÄ","VOIMA","SELVÄ","SYNTYÄ","OSOITTAA","TOIMINTA","ALKU","TAAS","NAINEN","VIIME","ENEMMÄN","NÄYTTÄÄ",
  19. "SEURAAVA","KÄSI","SUOMALAINEN","HETKI","OIKEA","KUULLA","TARKOITTAA","AINAKIN","KAUPUNKI","VALTIO","PYRKIÄ","TUTKIMUS","VAATIA","MERKITÄ",
  20. "PAIKKA","YLI","APU","LUKU","VAIKUTTAA","VARTEN","JOLLOIN","TOIMIA","HELSINKI","PERUSTE","TIETO","NIMI","LASKEA","ELI","EHKÄ","KIRKKO",
  21. "ENÄÄ","LAKI","TUNTUA","LIITTYÄ","MÄÄRÄTÄ","AUTO","HELPPO","PYKÄLÄ","VARSIN","KIRJA","JOUKKO","ESIINTYÄ","AJATELLA","JOKU","KUNTA","KUINKA",
  22. "KANTA","RAKENTAA","AIHEUTTAA","JEESUS","KÄSITELLÄ","ERITYINEN","HERRA","VUOKSI","HENKILÖ","MUUTAMA","VALITA","VASTAAN","ESIMERKKI","KOULU",
  23. "NOUSTA","SITEN","TILA","VASTA","ARVO","KULUA","LUKEA""TUTKIA","VASTAAVA","ISÄ","KASVAA","MAHDOLLISUUS","VIEDÄ","SIJA","ASETTAA","HALLITUS",
  24. "KÄYTTÖ","PARAS","ESIM.","EDELLÄ","MATKA","SAMALLA","VOIMAKAS","MM.","MUISTAA","TARKOITUS","MUODOSTAA","RYHMÄ","VAIKEA","KEHITYS","JÄTTÄÄ",
  25. "KOTI","VAIKUTUS","NOPEA","ERITTÄIN","TÄNÄÄN","KANSA","ÄITI","JOHTAA","JOHTUA","VÄHÄN","KULKEA","MARKKA","TÄLLÖIN","SEURATA","VASTATA","HUOMATA",
  26. "KORKEA","MUKAINEN","ODOTTAA","PERUSTAA","VALMISTAA","TUODA","EDELLEEN","SIIRTYÄ","YHTÄ","ERILAINEN","JATKUVA","JÄSEN","LIIKE","POIS","JOPA",
  27. "MUKANA","ILMAN","OIKEUS","PÄÄ","TILANNE","MUOTO","MYÖSKIN","TAVALLINEN","KAUNIS","KIRJOITTAA","LISÄTÄ","RUNSAS","SAMOIN","LÖYTÄÄ","ALA","SILMÄ",
  28. "SUHDE","MUUTTAA","JÄRJESTÄÄ","MUUTTUA","VARSINAINEN","VIIKKO","PYSTYÄ","VIIMEINEN","ILMOITTAA","KIELI","RUOTSI","ELÄÄ","TALOUDELLINEN","TALO",
  29. "TEKIJÄ","ENTINEN","LOPPU","OVI","PIIRI","ILMEINEN","USKOA","VÄLILLÄ","KOKOUS","MAKSAA","JOSKUS","KERRAN","LEHTI","SAAVUTTAA","LAAJA","PARI",
  30. "ASEMA","KUKA","KIINNITTÄÄ","KUKIN","MERKITYS","HOITAA","N.","NO","PÄÄTÖS","V.","YMMÄRTÄÄ","KAUTTA","PUU","HAVAITA","HUOLIA","LÄHES","TUNTI",
  31. "TÄYSIN","HETI","LIIAN","METRI","OPETTAJA","OPPILAS","RATKAISTA","ALOITTAA","METSÄ","PANNA","TULO","TYTTÖ","KRISTUS","PUOLESTA","TODELLA",
  32. "HYVÄKSYÄ","NYKYINEN","ISTUA","JOTEN","MOLEMMAT","SIKSI","ÄÄNI","EDUSTAJA","TARVE","HANKKIA","HENKI","YHÄ","AIKAISIN","KOLMAS","LIENEE","PERHE",
  33. "VALMIS","MUODOSTUA","SYDÄN","VAI","AUTTAA","POHJA","TEOS","TOISAALLA","NÄKYÄ","TÄYTTÄÄ","LÄHINNÄ","VIISI","JOTTA","PÄÄTTYÄ","JAKAA","JOKO",
  34. "KYMMENEN","LUODA","MYÖHEMMIN","NELJÄ","OIKEIN","TIETYSTI","KESÄ","KUKAAN","MUUTOS","TOIVOA","ILTA","JÄLLEEN","VARSINKIN","VERRATA","JATKAA",
  35. "MUUTEN","YHTEINEN","YRITTÄÄ","KYSYÄ","TAULUKKO","A","ASUA","KÄSITYS","JALKA","OHJELMA","SOTA","TAHTOA","KILPAILU","OSTAA","PROSENTTI","SOPIA",
  36. "AJAA","ILMA","PAHA","HINTA","VAIHE","LYHYT","OSATA","YHTEISKUNTA","AJATUS","ENSI","RIITTÄVÄ","SINNE","EDELLINEN","KESTÄÄ","PUHE","RATKAISU",
  37. "VARMASTI","ESITYS","KUTSUA","KÄSITTÄÄ","KÄYTÄNTÖ","LUOKKA","TIETTY","SOPIVA","TARJOTA","VALO","VOITTAA","AINE","AINOA","EDES","JOHTAJA","VERTA",
  38. "MIKSI","YÖ","MYÖNTÄA","NS.","ONGELMA","SAAPUA","TARKASTELLA","TOSIN","TÄYTYÄ","NEUVOSTOLIITTO","NIMENOMAAN","TAVATA","YKSITYINEN","HOITO",
  39. "RIIPPUA","SEURAKUNTA","AIHE","ALLE","SUUNNITELLA","HIEMAN","KEHITTÄÄ","RAKENNUS","KANSAINVÄLINEN","KOVA","OPPIA","PUUTTUA","PÄÄTTÄÄ","RIITTÄÄ",
  40. "RYHTYÄ","TOIMITTAA","ERO","KAUAN","KUUKAUSI","VÄHÄINEN","LAITOS","LÄHETTÄÄ","MIKÄLI","TAIVAS","HUOMATTAVA","HEIMO","KUHA",
  41.  
  42. "SIJOITTAA","SYÖDÄ","VAPAA","CM","KOSKAAN","KUVATA","MERKKI","PAITSI","PAREMPI","SATTUA","SELVITTÄÄ","TASO","TYÖNTEKIJÄ","AAMU","EDELLYTTÄÄ",
  43. "EDESSÄ","PYSYÄ","SARJA","TAVARA","TIETENKIN","VALTA","ENSIN","KIINNI","NOUDATTAA","PINTA","SUHTEELLINEN","SÄÄTÄÄ","AINOASTAAN","LISÄÄNTYÄ",
  44. "SYKSY","TUTUSTUA","PERUSTUA","TEHOKAS","VASEN","EDUSTAA","JOHTO","KOKONAAN","USKO","VARA","KOHTI","LUONTO","MELKO","RAJA","TOTEUTTAA","AVATA",
  45. "KOKEA","KUSTANNUS","TAVALLISESTI","TUOTANTO","VÄLINEN","YRITYS","ASTI","KASVU","KIVI","KOVIN","MK ","NOSTAA","PALATA","RANTA","VOITTO",
  46. "YLIOPISTO","HEIKKO","HUONE","JATKUA","KALA","KANTAA","KESKELLÄ","KOKEMUS","KONE","OSALLISTUA","POISTAA","TODELLINEN","POTILAS","PYYTÄÄ","SIJAITA",
  47. "VAIKEUS","EHTIÄ","ETU","LIIKKUA","NYKYISIN","PIAN","SAAKKA","SISÄLTÄÄ","VALLITA","ILMETÄ","SIVU","TOIMI","HAKEA","LAATIA","PUHEENJOHTAJA","SUUNTA",
  48. "YMPÄRILLÄ","ESTÄÄ","IKKUNA","LÄHELLÄ","PISTE","SEINÄ","VIERAS","HUOMATTAVASTI","KUMPIKIN","ONNISTUA","PRESIDENTTI","TOIMENPIDE","V","ERIKOINEN",
  49. "KOHDE","SIIRTÄÄ","TAKIA","YKSINKERTAINEN","ESILLÄ","ETSIÄ","K","MELKEIN","PAINAA","PUOLUE","VAHVISTAA","VETÄÄ","VIRKA","KANNATTAA","KOMITEA",
  50. "KUNINGAS","LÖYTÖRETKI","MÄÄRÄYS","TAKAISIN","TURKU","ILMESTYÄ","NUO","SEIKKA","TARPEELLINEN","AURINKO","KATSELLA","KEVÄT","MITATA","MUSTA",
  51. "TUULI","VAATIMUS","KELLO","KESKUSTELU","LAATU","PÄÄLLE","ALLA","KESKEN","KUOLEMA","LIITTO","LUULLA","LÄPI","TILAISUUS","ISO","JOHDOSTA","KIITOS",
  52. "KOHOTA","POIKETA","PYHÄ","SÄÄNNÖS","TAMPERE","TUOTTAA","ULKOPUOLI","YHDISTYS","MENO","MERI","NIMITTÄIN","PÖYTÄ","TÄNNE","VÄRI","ARVIOIDA","ELLEI",
  53. "KYLÄ","LÄMMIN","MILLOIN","PAREMMIN","RAHA","SOVELTAA","SYVÄ","YHDESSÄ","ASUNTO","OPETUS","PERIAATE","SUUNNITELMA","SÄILYTTÄÄ","YSTÄVÄ","KEHITTYÄ",
  54. "KUOLLA","TAPAHTUMA","JOUKKUE","KERÄTÄ","LOPULLINEN","RAKKAUS","TARKKA","PALKKA","PÄIN","RUOKA","SOSIAALINEN","TALVI","VASTAUS","LAULU","MYYDÄ",
  55. "SEURA","TUSKIN","VIETTÄÄ","EHDOTTAA","KOKONAISUUS","LAUSUA","MENETELMÄ","OLO","SUORAAN","VAARA","VARMAAN","YKSILÖ","EHDOTUS","KULJETTAA","PELÄTÄ",
  56. "PUNAINEN","RUOTSALAINEN","SATA","SISÄLTYÄ","VENE","JNE.","LÄMPÖTILA","MUUALLA","POLIITTINEN","SAIRAALA","SAMANLAINEN","TAKANA","TAVOITE",
  57. "VALITTAA","VALMISTUA","VIIMEKSI","EDUSKUNTA","KAI","KATU","LAJI","MILJOONA","SOITTAA","VALKOINEN","YHDISTÄÄ","YHTIÖ","EDELLYTYS","ESITELLÄ",
  58. "HISTORIA","HUONO","LINJA","LÄÄKÄRI","MIELIPIDE","OSASTO","OY.","RAAMATTU","TOSI","TSEKKOSLOVAKIA","TULEVA","VAIHDELLA","HAUSKA","HEITTÄÄ","KÄÄNTYÄ",
  59. "MINUUTTI","RAUHA","SEURAUS","SUHTAUTUA","VÄLITÖN","KIERTÄÄ","LYÖDÄ","MIHIN","MOMENTTI","PALVELUS","SILTI","SISÄINEN","SUU","TUNNETTU","UUDELLEEN",
  60. "AIKAINEN","HIDAS","ILO","LAPPI","MIELENKIINTOINEN","NORMAALI","OLOSUHDE","OPETTAA","PUDOTA","SIIHEN","SYNTI","TEOLLISUUS","TUKEA","VALTAKUNTA",
  61. "VARUSTAA","ELÄVÄ","JÄRVI","KILOMETRI","PIIRRE","PUHDAS","SEISOA","TUTTU","VAHVA","YHDYSVALLAT","YLEISÖ","ASTE","JULKAISTA","LAHJA","NUMERO",
  62. "PITUUS","SAKSA","SUINKAAN","VIITATA","AMERIKKALAINEN","EROTTAA","ETEEN","IKÄÄN","KORJATA","LAULAA","NAUTTIA","NÄHDEN","ONNI","SOPIMUS","SOVELTUA",
  63. "TASAINEN","VASTUU","YHTEENSÄ","YLLÄ","AIHEUTUA","ELÄIN","HALLITA","IHAN","IKÄ","KAIKKIAAN","KATTO","KAUPPA","KIELTÄÄ","LUKUMÄÄRÄ","LUONNOLLINEN",
  64. "PEITTÄÄ","RAJOITTAA","TYHJÄ","TÄYDELLINEN","VUORO","HENKINEN","KÄRSIÄ","OTTELU","PARANTAA","RADIO","VÄHINTÄÄN","ETEENPÄIN","EUROOPPA","HIUKAN",
  65. "HÄVITÄ","KOE","KUUNNELLA","KÄSITTELY","LAIVA","LIHA","M","MELKOINEN","MÄ","OMINAISUUS","PEKKA","POLIISI","SEITSEMÄN","TEKO","TULEVAISUUS",
  66. "VANHEMPI","VÄHEMMÄN","VÄLISSÄ","ANSIO","ASETUS","ERINOMAINEN","KESKUSTELLA","KIRJAILIJA","MENETTÄÄ","OSITTAIN","SAIRAUS","TAIKKA","TUOMITA",
  67. "VIRALLINEN","B","HUOLEHTIA","KENTTÄ","KIITTÄÄ","KIRJALLISUUS","KUUSI","MM","MUKAVA","NOJALLA","PÄÄLLÄ","RASKAS","S.","SULKEA","TAITAA","TEHDAS",
  68. "AVOIN","KALLIS","KOOTA","NEUVOTTELU","NIMITTÄÄ","PUUTE","RAKASTAA","SALLIA","TAHANSA","TEKNILLINEN","VALTIONEUVOSTO","VÄITTÄÄ","AINEISTO","ARVOKAS",
  69. "ELOKUVA","ENGLANTI","ESIIN","JOULU","JUTTU","KRISTITTY","KUIVA","KUNTO","LOPETTAA","LUMI","MAASEUTU","MAKSU","NYKYÄÄN","PAINO","YM.","YMPÄRISTÖ",
  70. "EILEN","HERÄTTÄÄ","ILMOITUS","JONKINLAINEN","JULKINEN","KIINTEÄ","KÄYTÄNNÖLLINEN","MEKSIKO","OHI","OHJE","SUORA","TAISTELU","TUOTE","VARMA",
  71. "VÄLTTÄMÄTÖN","YKSIN","HUOLI","JÄRJESTELMÄ","LAUSUNTO","LIIKENNE","LUONNE","NOUSU","NUORISO","OMISTAA","OSUUS","SELITTÄÄ","TAITO","UNOHTAA",
  72. "VAPAUS","VUOSISATA","AIKOA","ALAINEN","ERÄ","ILMAISTA","KOHTAAN","KRISTILLINEN","KYLMÄ","LINTU","MERKITTÄVÄ","OHJATA","PALVELLA","POHJOINEN",
  73. "ROUVA","SAARI","SUNNUNTAI","ULOS","VOI","ENTÄ","EROTA","HARJOITTAA","HUUTAA","KAHDEKSAN","KORVAUS","LIITTÄÄ","MUASSA","OLETTAA","TOISTAINEN",
  74. "VAHINKO","HIENO","ISÄNTÄ","JUOSTA","KASVOT","KESKEINEN","KIRJE","KOIRA","LUONNOLLISESTI","LÖYTYÄ","NÄKYVÄ","NÄYTE","PAPPI","SELVITÄ","SÄILYÄ",
  75. "VAKAVA","ASIANOMAINEN","ENITEN","ILOINEN","JÄLKI","KAIKKIALLA","KEITTIÖ","LUKUISA","MILTEI","NÄKÖINEN","OPISKELIJA","OSOITTAUTUA","PAIKALLINEN"]
  76.  
  77. #vocab = ["AJELU","AJO","AJOS","AJOSSA","AJAA","AJATUS"] #, "AB"]
  78.  
  79.  
  80.  
  81. class Trie:
  82. __data = {}
  83. __EOS = '$' #regexp end of string
  84.  
  85. def __add(self, word):
  86. cur = self.__data
  87.  
  88. for c in word:
  89. if c not in cur:
  90. cur[c] = {}
  91. cur = cur[c]
  92.  
  93. cur[self.__EOS] = self.__EOS
  94.  
  95.  
  96. def add(self, par):
  97. if isinstance(par, (list,set,tuple)):
  98. for a in par:
  99. self.__add(a)
  100. else:
  101. self.__add(par)
  102.  
  103.  
  104. def find(self, word):
  105. cur = self.__data
  106.  
  107. for c in word:
  108. if c not in cur:
  109. return False
  110. cur = cur[c]
  111.  
  112. return cur
  113.  
  114.  
  115. def _iter(self, path, trie):
  116. if self.__EOS in trie:
  117. yield path
  118.  
  119. for c in trie:
  120. if c != self.__EOS:
  121. for result in self._iter(path + c, trie[c]):
  122. yield result
  123.  
  124.  
  125. def reduce(self, key):
  126. a = self.find(key)
  127. if not a:
  128. return []
  129. else:
  130. return [x for x in self._iter(key, a)]
  131.  
  132.  
  133. def show(self):
  134. print(self.__data)
  135.  
  136.  
  137. __getitem__ = find
  138.  
  139.  
  140.  
  141. trie = Trie()
  142. trie.add(vocab)
  143.  
  144. #trie.show()
  145.  
  146. print( trie.reduce("SU") )
  147. #print( trie.reduce("AJ") )
Add Comment
Please, Sign In to add comment