Использование дерева в python для получения значений

Итак, я пытаюсь создать дерево с помощью Python, чтобы иметь возможность попытаться прочитать текстовый файл, в котором есть повторяющиеся количества в файле, и попытаться создать дерево из этих значений и вернуть предложения с верхними значениями 3 (объяснено более подробно ниже).

Прежде всего я искал в википедии информацию о том, как создается дерево, а также видел предыдущие примеры в stackoverflow, например: Этот. и это. Однако я смог сделать это только до тех пор, пока идет код:

import fileinput

setPhrasesTree = 0


class Branch():
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

class Tree():
    def __init__(self):
        self.root = None
        self.found = False

    #lessThan function needed to compare strings
    def lessThan(self, a, b):    
        if len(a) < len(b):
            loopCount = len(a)
        else:
            loopCount = len(b)        
        for pos in range(0, loopCount):
            if a[pos] > b[pos]:
                return False        
        return True

    def insert(self, value):
        self.root = self.insertAtBranch(self.root, value)

    def exists(self, value):
        #set the class variable found to False to assume it is not there      
        self.found = False
        self.findAtBranch(self.root, value)
        return self.found

    #Used to fine a value in a tree
    def findAtBranch(self, branch, value):        
        if branch == None:
            pass
        else:
            if branch.value == value:
                self.found = True                
            else:
                self.findAtBranch(branch.left, value)
                self.findAtBranch(branch.right, value)        

    def insertAtBranch(self, branch, value):
        if branch == None:
            return Branch(value)
        else:
            if self.lessThan(branch.value, value):
                branch.right = self.insertAtBranch(branch.right, value)            
            else:
                branch.left = self.insertAtBranch(branch.left, value)
            return branch

def loadTree(filename, treeType):

    if treeType == setPhrasesTree:
        for sentence in fileinput.input("setPhrases.txt"):
            print(sentence)
            setPhrases.insert(sentence[:-1])


def findSentenceType(sentence):

    if sentence.exists(sentence):
        return setPhrasesTree

Вот как выглядит текстовый файл. Имейте в виду, что он специально расположен так, а не со значением количества рядом с ним (имя файла = setPhrases.txt):

Hi my name is Dave.
Thank-You.
What is your name?
I have done all my homework.
What time is dinner?
What is your name?
Thank-You.
Hi my name is Dave.
What is your name?
I have done all my homework.
What is your name?
Can you bring me a drink Please?
Can you bring me a drink Please?
What is your name?
Hi my name is Dave.
What is your name?
Can you bring me a drink Please?

Вот что я пытаюсь сделать, чтобы мой код делал. Мне нужно, чтобы он распознал, что первое предложение в файле является начальным узлом. Затем ему нужно подсчитать все другие предложения, которые совпадают, и добавить значение к этому предложению, и просто использовать дерево, чтобы сделать это. (Первоначально я сделал это другим способом, однако мне нужно использовать дерево, чтобы иметь возможность подсчитывать и делать все остальные вещи) Вот что я имею в виду: введите здесь описание изображения

Затем я хочу иметь возможность вернуть 3 лучших Phrases с самыми высокими частотами. Таким образом, в этом случае система вернет предложения (в таком порядке):

What is your name?
Hi my name is Dave.
Can you bring me a drink please?

Любая помощь горячо приветствуется. Также спасибо за ваше время.


person PythonNovice    schedule 05.02.2014    source источник
comment
Я правильно понимаю, вы просто хотите посчитать, как часто каждая строка присутствует в файле? Для этого вряд ли понадобится дерево.   -  person pentadecagon    schedule 05.02.2014
comment
@pentadecagon Верно, и, как я уже упоминал ранее, я уже смог это сделать. Однако мне нужно сделать это с помощью дерева, и я понятия не имею, что делать дальше.   -  person PythonNovice    schedule 06.02.2014
comment
Требуется дерево? Так это упражнение? Просто чтобы быть уверенным, потому что вы знаете, что эту проблему можно решить более эффективно, используя словарь вместо дерева примерно в 20 строках кода. Если вы действительно хотите дерево, то для того, чтобы дерево было полезным, оно, вероятно, должно быть чем-то вроде самобалансирующееся дерево, наиболее популярным здесь является красно-черное дерево. Это довольно большая работа, которую нужно реализовать самостоятельно.   -  person pentadecagon    schedule 06.02.2014
comment
@pentadecagon Можете ли вы показать мне, как сделать это по-своему, а также реализовать способ, чтобы пользователь мог выбрать вариант, и он добавит +1 к подсчету в текстовом файле?   -  person PythonNovice    schedule 07.02.2014
comment
Что вы подразумеваете под счетом в текстовом файле? Как бы это выглядело?   -  person pentadecagon    schedule 07.02.2014


Ответы (1)


Вот она, реализация с использованием словаря. Это то, что вы хотите?

import collections
def count_lines():
    d = collections.defaultdict(int)
    for line in open( "phrases.txt" ):
        d[ line.strip() ] += 1

    # we use the negative count as sort key, so the biggest ends up first
    a = sorted( d.items(), key=lambda x : -x[1] )
    for n, u in enumerate( a[:3] ):
        print( u[0], "# count=", u[1] )

count_lines()        
person pentadecagon    schedule 07.02.2014