Search in a big dictionary Python

Question

I have a big Python dictionary with more then 150,000 keys every key has list value. This dictionary contains infinitive words as key and all grammatical forms of these words as values:

 {"конфузити": ["конфузить", "конфужу", "конфузиш", "конфузить", "конфузим", "конфузимо", "конфузите", "конфузять", "конфузитиму", "конфузитимеш", "конфузитиме", "конфузитимем", "конфузитимемо", "конфузитимете", "конфузитимуть", "конфузив", "конфузила", "конфузило", "конфузили"]}  

I formed list of words from particular text there are more then 2m words in it, every word has it's grammatical form. So what I am trying to do is searching these words in my dictionary values and returning dictionary keys, which as I have already told, are base or dictionary forms of words. This process is called lemmatization. Have tried different approaches but they are all too slow.

In this part I perform text tokenization.

lst =[]
with open("/home/yan/PycharmProjects/vk/my_patrioty/men_patrioty.txt", 'r', encoding="utf-8") as f:
    for sent in f:
        sent = sent.lower()
        sent = re.sub("[A-z0-9\'\"`\|\/\+\#\,\)\(\?\!\B\-\:\=\;\.\«\»\—\@]", '', sent)
        sent = re.findall('\w+', sent)
        for word in sent:
            lst.append(word)

In this part I am trying to perform binary search but is very slow.

with open("/home/yan/data.txt") as f:
    d = json.load(f)
    for w in lst:   #list of my words
        for key, value in d.items():
            lb = 0
            ub = len(value)
            mid_index = (lb + ub) // 2
            item_at_mid = value[mid_index]
            if item_at_mid == w:
                    print(key)
            if item_at_mid < w:
                    lb = mid_index + 1
            else:
                ub = mid_index

This is liner search it is a bit faster. But still not enough fast for my amount of data.

with open("/home/yan/data.txt") as f:
    d = json.load(f)  #dictionary to search in
    for w in lst:
        for key, value in d.items():
              if w in value:
                  print(key)

Below you can find links to my dictionary and sample of data to test it. If somebody does not know it is Ukrainian language that is presented in data set.

Dictionary data:

https://drive.google.com/file/d/0ByIY5scTeLYqbXp6OExKa0xXbDg/view?usp=sharing

Sample of text:

https://drive.google.com/file/d/0ByIY5scTeLYqMHhHbUJ5aXRWdWs/view?usp=sharing

Answer 1

I'd suggest turning the problem around. A dictionary is really good for looking up the key, but not for finding a key for a specific value.

First, you need to convert your dictionary to a dictionary in reverse:

with open("/home/yan/data.txt") as f:
    kv_dict = json.load(f)

vk_dict = {}
for k, vs in kv_dict.items():
    for v in vs:
        vk_dict.setdefault(v, []).append(k)

with open("/home/yan/data_rev.txt", "w") as f:
    json.dump(vk_dict, f)

Then, in your code, you can just write

with open("/home/yan/data_rev.txt") as f:
    d = json.load(f)

for w in list:
    for k in d.get(w, [])
        print(k)

The advantage: building data_rev.txt only needs to be done when data.txt changes, which is hopefully not that often.

Answer 2

Do not iterate over the whole dictionary, most of the entries shouldn't be considered at all. You need a preliminary stage to select viable candidates.

One possible approach is to have a sorted list of base forms. Now given a word, find its lower and upper bounds, and inspect only base forms in this range.

From a cursory look at your dictionary, I would suggest to modify it slightly. Move the base form into the paradigm, and let key be a longest common prefix. Limit the search range same way as above.

It may (and will) fail in some corner cases. Alternation, reduction, etc, must be addressed separately.

Edit:

The modified dictionary would look like

{"конфу": ["зити", "зить", "жу", "зиш", "зить", "зим", "зимо", "зите", "зять", "зитиму", "зитимеш", "зитиме", "зитимем", "зитимемо", "зитимете", "зитимуть", "зив", "зила", "зило", "зили"]}

The key could be made a bit longer, but then you'd have to account for з-ж alternation; would it be beneficial or detrimental depends on access pattern.

Answer 3

I have found solution to my issue, maybe not the best but it works much faster than my previous approaches. Basically I modified my dictionary, example of it you can see in my question. Now it is json lines file
And when I perform liner search on it and works much faster because it returns not word by word as it was before but all words in the same time. For example if there are 10 words working in my list it will lematize 10 of them at the same time. In 40 min it has lematized 30,000 words.

Dump into json lines:

def dumping_into_json(input_file, output):
    with open(input_file, encoding='utf-8', errors='ignore') as f:
        for i in file:
            with open(output, 'a', encoding='utf-8') as file1:
                file1.write('%s\n' % json.dumps(i, ensure_ascii=False))  

Liner search:

with open("/home/yan/lem") as lem:
    for i in lem:
        i = json.loads(i)
        for w in lst:
            for key, value in i.items():
                if w in value:
                    print(key)