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