Python package for lexicon
Project description
Lexpy
-
A lexicon is a data-structure which stores a set of words. The difference between a dictionary and a lexicon is that in a lexicon there are no values associated with the words.
-
A lexicon is similar to a list or a set of words, but the internal representation is different and optimized for faster searches of words, prefixes and wildcard patterns.
-
Given a word, precisely, the search time is O(W) where W is the length of the word.
-
2 important lexicon data-structures are Trie and Directed Acyclic Word Graph (DAWG).
Install
lexpy
can be installed via Python Package Index (PyPI)
using pip
. The only installation requirement is that you need Python 3.7 or higher.
pip install lexpy
Interface
Interface Description | Trie | DAWG |
---|---|---|
Add a single word | add('apple', count=2) |
add('apple', count=2) |
Add multiple words | add_all(['advantage', 'courage']) |
add_all(['advantage', 'courage']) |
Check if exists? | in operator |
in operator |
Search using wildcard expression | search('a?b*', with_count=True) |
search('a?b*, with_count=True) |
Search for prefix matches | search_with_prefix('bar', with_count=True) |
search_with_prefix('bar') |
Search for similar words within given edit distance. Here, the notion of edit distance is same as Levenshtein distance | search_within_distance('apble', dist=1, with_count=True) |
search_within_distance('apble', dist=1, with_count=True) |
Get the number of nodes in the automaton | len(trie) |
len(dawg) |
Examples
Trie
Build from an input list, set, or tuple of words.
from lexpy import Trie
trie = Trie()
input_words = ['ampyx', 'abuzz', 'athie', 'athie', 'athie', 'amato', 'amato', 'aneto', 'aneto', 'aruba',
'arrow', 'agony', 'altai', 'alisa', 'acorn', 'abhor', 'aurum', 'albay', 'arbil', 'albin',
'almug', 'artha', 'algin', 'auric', 'sore', 'quilt', 'psychotic', 'eyes', 'cap', 'suit',
'tank', 'common', 'lonely', 'likeable' 'language', 'shock', 'look', 'pet', 'dime', 'small'
'dusty', 'accept', 'nasty', 'thrill', 'foot', 'steel', 'steel', 'steel', 'steel', 'abuzz']
trie.add_all(input_words) # You can pass any sequence types or a file-like object here
print(trie.get_word_count())
>>> 48
Build from a file or file path.
In the file, words should be newline separated.
from lexpy import Trie
# Either
trie = Trie()
trie.add_all('/path/to/file.txt')
# Or
with open('/path/to/file.txt', 'r') as infile:
trie.add_all(infile)
Check if exists using the in
operator
print('ampyx' in trie)
>>> True
Prefix search
print(trie.search_with_prefix('ab'))
>>> ['abhor', 'abuzz']
print(trie.search_with_prefix('ab', with_count=True))
>>> [('abuzz', 2), ('abhor', 1)]
Wildcard search using ?
and *
-
?
= 0 or 1 occurrence of any character -
*
= 0 or more occurrence of any character
print(trie.search('a*o*'))
>>> ['amato', 'abhor', 'aneto', 'arrow', 'agony', 'acorn']
print(trie.search('a*o*', with_count=True))
>>> [('amato', 2), ('abhor', 1), ('aneto', 2), ('arrow', 1), ('agony', 1), ('acorn', 1)]
print(trie.search('su?t'))
>>> ['suit']
print(trie.search('su?t', with_count=True))
>>> [('suit', 1)]
Search for similar words using the notion of Levenshtein distance
print(trie.search_within_distance('arie', dist=2))
>>> ['athie', 'arbil', 'auric']
print(trie.search_within_distance('arie', dist=2, with_count=True))
>>> [('athie', 3), ('arbil', 1), ('auric', 1)]
Increment word count
- You can either add a new word or increment the counter for an existing word.
trie.add('athie', count=1000)
print(trie.search_within_distance('arie', dist=2, with_count=True))
>>> [('athie', 1003), ('arbil', 1), ('auric', 1)]
Directed Acyclic Word Graph (DAWG)
-
DAWG supports the same set of operations as a Trie. The difference is the number of nodes in a DAWG is always less than or equal to the number of nodes in Trie.
-
They both are Deterministic Finite State Automata. However, DAWG is a minimized version of the Trie DFA.
-
In a Trie, prefix redundancy is removed. In a DAWG, both prefix and suffix redundancies are removed.
-
In the current implementation of DAWG, the insertion order of the words should be alphabetical.
-
The implementation idea of DAWG is borrowed from http://stevehanov.ca/blog/?id=115
from lexpy import Trie, DAWG
trie = Trie()
trie.add_all(['advantageous', 'courageous'])
dawg = DAWG()
dawg.add_all(['advantageous', 'courageous'])
len(trie) # Number of Nodes in Trie
23
dawg.reduce() # Perform DFA minimization. Call this every time a chunk of words are uploaded in DAWG.
len(dawg) # Number of nodes in DAWG
21
DAWG
The APIs are exactly same as the Trie APIs
Build a DAWG
from lexpy import DAWG
dawg = DAWG()
input_words = ['ampyx', 'abuzz', 'athie', 'athie', 'athie', 'amato', 'amato', 'aneto', 'aneto', 'aruba',
'arrow', 'agony', 'altai', 'alisa', 'acorn', 'abhor', 'aurum', 'albay', 'arbil', 'albin',
'almug', 'artha', 'algin', 'auric', 'sore', 'quilt', 'psychotic', 'eyes', 'cap', 'suit',
'tank', 'common', 'lonely', 'likeable' 'language', 'shock', 'look', 'pet', 'dime', 'small'
'dusty', 'accept', 'nasty', 'thrill', 'foot', 'steel', 'steel', 'steel', 'steel', 'abuzz']
dawg.add_all(input_words)
dawg.reduce()
dawg.get_word_count()
>>> 48
Check if exists using the in
operator
print('ampyx' in dawg)
>>> True
Prefix search
print(dawg.search_with_prefix('ab'))
>>> ['abhor', 'abuzz']
print(dawg.search_with_prefix('ab', with_count=True))
>>> [('abuzz', 2), ('abhor', 1)]
Wildcard search using ?
and *
?
= 0 or 1 occurance of any character
*
= 0 or more occurance of any character
print(dawg.search('a*o*'))
>>> ['amato', 'abhor', 'aneto', 'arrow', 'agony', 'acorn']
print(dawg.search('a*o*', with_count=True))
>>> [('amato', 2), ('abhor', 1), ('aneto', 2), ('arrow', 1), ('agony', 1), ('acorn', 1)]
print(dawg.search('su?t'))
>>> ['suit']
print(dawg.search('su?t', with_count=True))
>>> [('suit', 1)]
Search for similar words using the notion of Levenshtein distance
print(dawg.search_within_distance('arie', dist=2))
>>> ['athie', 'arbil', 'auric']
print(dawg.search_within_distance('arie', dist=2, with_count=True))
>>> [('athie', 3), ('arbil', 1), ('auric', 1)]
Alphabetical order insertion
If you insert a word which is lexicographically out-of-order, ValueError
will be raised.
dawg.add('athie', count=1000)
ValueError
ValueError: Words should be inserted in Alphabetical order. <Previous word - thrill>, <Current word - athie>
Increment the word count
- You can either add an alphabetically greater word with a specific count or increment the count of the previous added word.
dawg.add_all(['thrill']*20000) # or dawg.add('thrill', count=20000)
print(dawg.search('thrill', with_count=True))
>> [('thrill', 20001)]
Special Characters
Special characters, except ?
and *
, are matched literally.
from lexpy import Trie
t = Trie()
t.add('a©')
t.search('a©')
>> ['a©']
t.search('a?')
>> ['a©']
t.search('?©')
>> ['a©']
Trie vs DAWG
Future Work
These are some ideas which I would love to work on next in that order. Pull requests or discussions are invited.
- Merge trie and DAWG features in one data structure
- Support all functionalities and still be as compressed as possible.
- Serialization / Deserialization
- Pickle is definitely an option.
- Server (TCP or HTTP) to serve queries over the network.
Fun Facts
- The 45-letter word pneumonoultramicroscopicsilicovolcanoconiosis is the longest English word that appears in a major dictionary. So for all english words, the search time is bounded by O(45).
- The longest technical word(not in dictionary) is the name of a protein called as titin. It has 189,819 letters and it is disputed whether it is a word.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
File details
Details for the file lexpy-1.1.0.tar.gz
.
File metadata
- Download URL: lexpy-1.1.0.tar.gz
- Upload date:
- Size: 28.4 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.10.14
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0c6c92a768fecade1d6e4acf95e5c5908f5bd5d19e3ce57ed1a26075e03576a9 |
|
MD5 | 6a20896e847add4834071072b925640b |
|
BLAKE2b-256 | 97e1954f0a8d4e49e4b78ee111d0a3cc6fa6cee05040411fde20d15ade5682e0 |
File details
Details for the file lexpy-1.1.0-py3-none-any.whl
.
File metadata
- Download URL: lexpy-1.1.0-py3-none-any.whl
- Upload date:
- Size: 27.5 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/4.0.2 CPython/3.10.14
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 50fd02c97c832de10a6a1e8c84587cef98f21035c9f4092f7e95a5dabe6d0837 |
|
MD5 | 684606454e324397c538eb77289d2de9 |
|
BLAKE2b-256 | a81841917f8c907e53a7843fecef554c68f36467edc070f0f5f4f7bfd341e229 |