تنفيذ Trie Patricia لاستخدامه كشركة

Question

أحاول تنفيذ Trie Patricia مع الأساليب addWord(), isWord(), ، و isPrefix() كوسيلة لتخزين قاموس كبير للكلمات لاسترجاع سريع (بما في ذلك البحث البادئة). لقد قرأت على المفاهيم لكنها لا توضح فقط في التنفيذ. أريد أن أعرف (في Java أو Python Code) كيفية تنفيذ Trie، خاصة العقد (أو يجب أن أقوم بتطبيقها بشكل متكرر). رأيت شخصا واحدا نفذته بمجموعة من 26 عقدة تابعة لها إلى NULL / NOUL. هل هناك استراتيجية أفضل (مثل علاج الحروف كطبقات) وكيف تنفذها؟

Answer 1

سأل شخص آخر سؤال عن باتريشيا منذ فترة وكنت فكرت في إجراء تنفيذ ثعبان إذن، لكن هذه المرة قررت أن أعطها في الواقع طلقة (نعم، هذه طريقة رائعة، ولكن يبدو وكأنه مشروع صغير لطيف). ما الذي أحرزته هو عدم تطبيق باتريشيا النقي، لكني أحب طريقي بشكل أفضل. يحاول Patricia الأخرى (بلغات أخرى) (بلغات أخرى) مجرد قائمة للأطفال وتحقق من كل طفل لمعرفة وجود تطابق، لكنني اعتقدت أن هذا كان غير فعال حتى أقدم القواميس. هنا في الأساس كيف قمت بإعداده:

سأبدأ في عقدة الجذر. الجذر هو مجرد قاموس. يحتوي القاموس على مفاتيح هي جميع الأحرف الفردية (الأحرف الأولى من الكلمات) مما يؤدي إلى فروع. القيم المقابلة مع كل مفتاح هي قوائم حيث يعد العنصر الأول سلسلة تمنح بقية السلسلة التي تتطابق مع هذا الفرع Trie، والعنصر الثاني هو قاموس يؤدي إلى المزيد من الفروع من هذه العقدة. يحتوي هذا القاموس أيضا على مفاتيح حرف واحدة تتوافق مع الحرف الأول من بقية الكلمة وستستمر العملية في التركي.

شيء آخر يجب أن أذكره هو أنه إذا كانت عقدة معينة تحتوي على فروع، ولكن أيضا كلمة في Trie نفسها، ثم يتم الإشارة إلى ذلك '' مفتاح في القاموس الذي يؤدي إلى عقدة مع القائمة ['',{}].

إليك مثال صغير يظهر كيف يتم تخزين الكلمات (العقدة الجذرية هي المتغير _d):

>>> x = patricia()
>>> x.addWord('abcabc')
>>> x._d
{'a': ['bcabc', {}]}
>>> x.addWord('abcdef')
>>> x._d
{'a': ['bc', {'a': ['bc', {}], 'd': ['ef', {}]}]}
>>> x.addWord('abc')
{'a': ['bc', {'a': ['bc', {}], '': ['', {}], 'd': ['ef', {}]}]}

لاحظ أنه في الحالة الأخيرة، تمت إضافة مفتاح إلى القاموس للإشارة إلى أن "ABC" هي كلمة بالإضافة إلى "ABCDEF" و "Abcabc".

مصدر الرمز

class patricia():
    def __init__(self):
        self._data = {}

    def addWord(self, word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                if data:
                    data[word[i:i+1]] = [word[i+1:],{}]
                else:
                    if word[i:i+1] == '':
                        return
                    else:
                        if i != 0:
                            data[''] = ['',{}]
                        data[word[i:i+1]] = [word[i+1:],{}]
                return

            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            data = node[1]
                            data[''] = ['',{}]
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                ii = i
                j = 0
                while ii != len(word) and j != len(node[0]) and \
                      word[ii:ii+1] == node[0][j:j+1]:
                    ii += 1
                    j += 1
                tmpdata = {}
                tmpdata[node[0][j:j+1]] = [node[0][j+1:],node[1]]
                tmpdata[word[ii:ii+1]] = [word[ii+1:],{}]
                data[word[i-1:i]] = [node[0][:j],tmpdata]
                return

    def isWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                        except KeyError:
                            return False
                    return True
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                return False

    def isPrefix(self,word):
        data = self._data
        i = 0
        wordlen = len(word)
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                return False
            i += 1
            if word.startswith(node[0][:wordlen-i],i):
                if wordlen - i > len(node[0]):
                    i += len(node[0])
                    data = node[1]
                else:
                    return True
            else:
                return False

    def removeWord(self,word):
        data = self._data
        i = 0
        while 1:
            try:
                node = data[word[i:i+1]]
            except KeyError:
                print "Word is not in trie."
                return
            i += 1
            if word.startswith(node[0],i):
                if len(word[i:]) == len(node[0]):
                    if node[1]:
                        try:
                            node[1]['']
                            node[1].pop('')
                        except KeyError:
                            print "Word is not in trie."
                        return
                    data.pop(word[i-1:i])
                    return
                else:
                    i += len(node[0])
                    data = node[1]
            else:
                print "Word is not in trie."
                return


    __getitem__ = isWord

ربما لاحظت أنه في النهاية وضعت __getitem__ إلى طريقة istword. هذا يعني ذاك

x['abc']

سيعود سواء "ABC" في الثلاثي أم لا.

أعتقد أنه ربما يجب أن أقوم بإخراج وحدة واحدة من هذا وقم بإرساله إلى Pypi، لكنه يحتاج إلى مزيد من الاختبار وطريقة إيقاف كاملة على الأقل. إذا وجدت أي أخطاء، فأخبرني بذلك، لكن يبدو أنه يعمل بشكل جيد للغاية. أيضا، إذا رأيت أي تحسينات كبيرة في الكفاءة، أود أيضا أن أسمع عنها. لقد فكرت في فعل شيء ما حول وجود قواميس فارغة في أسفل كل فرع، لكنني سأتركها الآن. قد يتم استبدال هذه القواميس الفارغة بالبيانات المرتبطة بالكلمة لتوسيع استخدامات التنفيذ على سبيل المثال.

على أي حال، إذا كنت لا تحب الطريقة التي قمت بها، فقد تعطيك هذا على الأقل بعض الأفكار حول كيفية تطبيق الإصدار الخاص بك.

Answer 2

إليك تطبيقا متكررا باستخدام أساليب أثيرة:

def matching_prefix_index(word1, word2):
    max_len = min(len(word1),len(word2))
    for i in range(max_len):
        if word2[i] != word1[i]:
            return i
    return max_len

class PatriciaTrie(object):
    def __init__(self):
        self._storage = {}
        self._complete_prefix_flag = False

    def _find_storage_key(self, word):
        for key in self._storage:
            prefix_index = matching_prefix_index(key, word)
            if prefix_index > 0:
                return (key, prefix_index)
        return (None, None)

    def add(self, word):
        if word == '':
            self._complete_prefix_flag = True
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is not None:
            if prefix_index == len(key):
                return self._storage[key].add(word[len(key):])
            else:
                new_tree = PatriciaTrie()
                new_tree._storage[key[prefix_index:]] = self._storage.pop(key)
                self._storage[key[0:prefix_index]] = new_tree
                return new_tree.add(word[prefix_index:])
        else:
            self._storage[word] = PatriciaTrie()
            self._storage[word].add('')
            return True

    def remove(self, word):
        if word == '':
            self._complete_prefix_flag = False
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False

        subword = word[prefix_index:]
        subtrie = self._storage[key]
        if subtrie.remove(subword):
            if (not subtrie._complete_prefix_flag) and len(subtrie._storage) == 0:
                self._storage.pop(key)
            return True
        else:
            return False

    def __contains__(self, word):
        if word == '':
            return self._complete_prefix_flag

        key, prefix_index = self._find_storage_key(word)
        if key is None or prefix_index != len(key):
            return False
        else:
            return (word[prefix_index:] in self._storage[key])

    def has_prefix(self, word):
        if word == '':
            return True

        key, prefix_index = self._find_storage_key(word)
        if key is None:
            return False
        elif len(key) > len(word):
            return (prefix_index == len(word))
        elif len(key) != prefix_index:
            return False
        else:
            return self._storage[key].has_prefix(word[prefix_index:])