GoogleAutoComplete/TrieComplete.py at main · matan1346/GoogleAutoComplete · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
from dataclasses import dataclass

replace_char = {0: 5, 1: 4, 2: 3, 3: 2}
remove_char = {0: 10, 1: 8, 2: 6, 3: 4}

@dataclass
class SourceData:
    file_name: str
    line_number: int
    offset: int
    score: int


@dataclass
class TrieAutoComplete:
    def __init__(self):
        self.chars = {}
        self.end_of_word = False
        self.source_data = []

    def set_end_of_word(self, flag):
        self.end_of_word = flag

    def insert_word(self, word, source_data):
        if word == '':
            self.end_of_word = True
            self.source_data.append(source_data)
        else:
            c = word[0]
            if c not in self.chars:
                self.chars[c] = TrieAutoComplete()
            self.chars[c].insert_word(word[1:], source_data)

    @classmethod
    def minimize_results(cls, results):
        data = set()
        s = ''

        sorted_results = sorted(results, key=lambda s: len(s), reverse=True)
        for result in sorted_results:
            found = False
            # for item in data:
            #    if result.startswith(item):


    def search_prefix(self, s, prefix, flag=False, level = 0, score = 0): # pithon
        # print(s, self.end_of_word)
        res = []
        score += 2
        if s == '':
            return self.collect_words(prefix, score - 2)
        elif s[0] in self.chars:

            res = self.chars[s[0]].search_prefix(s[1:], prefix + s[0], flag, level + 1, score)
            if res:

                return res
        if not flag:
            for c, item in self.chars.items():
                # replace other char
                if level > 3:
                    current_score = score - 1
                else:
                    current_score = score - replace_char[level]

                current_res = self.chars[c].search_prefix(s[1:], prefix + c, True, level + 1, current_score)
                if current_res:
                    res.extend(current_res)

                # add other char
                if level > 3:
                    current_score = score - 2
                else:
                    current_score = score - remove_char[level]

                current_res = self.chars[c].search_prefix(s, prefix + c, True, level, current_score - 2)
                if current_res:
                    res.extend(current_res)

                if level > 3:
                    current_score = score - 2
                else:
                    current_score = score - remove_char[level]

                # ignore char
                if len(s) > 2:
                    current_res = self.chars[c].search_prefix(s[2:], prefix + s[1], True, level + 1, current_score)
                    if current_res:
                        res.extend(current_res)
            return res

    def collect_words(self, prefix, score = 0):
        res = []

        if self.end_of_word:
            res.append((prefix, self.source_data, score))

        #current_res = []
        for c, item in self.chars.items():
            # print(item.chars)
            res.extend(item.collect_words(prefix + c, score))
        #if current_res:
        #    return current_res
        # print(res)
        return res


def print_trie(tr, sentence = '', level = 0):
    if tr is None:
        return
    print('*'*level, 'level: ', level)
    if tr.end_of_word:
        print('*'*level, 'word:', sentence)
    for c, item in tr.chars.items():
        print_trie(item, sentence + c, level + 1)