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

  • So, given a particular form of a word, you want to efficiently come up with the infinitive version? – coderodde Mar 31 '16 at 16:06
  • Yes, I want to get infinitive of words in the text. – Yan Mar 31 '16 at 16:28
up vote 2 down vote accepted

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.

  • 2
    Isn't v a list? so you'd need something like {k: i for k, v in kv_dict for i in v}? – Peilonrayz Mar 31 '16 at 16:34
  • Yes. Bit of a typo. Also need to add something to handle value-clashes. I'll edit later. – Sjoerd Job Postmus Mar 31 '16 at 18:05
  • gives error TypeError: unhashable type: 'list' – Yan Mar 31 '16 at 20:06
  • Made an edit. Idea was to use each seperate word as key mapping back to its stem, it should work now. – Sjoerd Job Postmus Mar 31 '16 at 20:38
  • Yes, I made it before thanks, just wanted to show how to improve your answer. – Yan Mar 31 '16 at 20:53

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.

  • Your approach is very good I just use set() on my word list and now I have 242,954 words before had 2,299,535. Now it will be way faster. – Yan Apr 1 '16 at 9:37
  • Move the base form into the paradigm, and let key be a longest common prefix. Did not get what do you mean by this? Can you provide an example? – Yan Apr 3 '16 at 9:57
  • 1
    @Yan See the edit – vnp Apr 3 '16 at 21:52

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)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.