Бинарный поиск с использованием цикла for, поиск слов в списке и сравнение - PullRequest
Новая
       12

Бинарный поиск с использованием цикла for, поиск слов в списке и сравнение

0 голосов
/ 16 декабря 2018

Я пытаюсь сравнить слова в "alice_list" с "dictionary_list", и если слово не найдено в "dictionary_list", чтобы напечатать его и сказать, что оно, вероятно, написано с ошибкой.У меня проблемы, когда он ничего не печатает, если его не нашли, может, вы, ребята, могли бы мне помочь.У меня есть «alice_list», добавляемый в верхний регистр, так как «dictionary_list» все прописные.Любая помощь с тем, почему он не работает, будет принята с благодарностью, так как я собираюсь вырвать мои волосы на нем!

       import re
    # This function takes in a line of text and returns
    # a list of words in the line.

    def split_line(line):
        return re.findall('[A-Za-z]+(?:\'[A-Za-z]+)?', line)
    # --- Read in a file from disk and put it in an array.

    dictionary_list = []
    alice_list = []
    misspelled_words = []

    for line in open("dictionary.txt"):
        line = line.strip()
        dictionary_list.extend(split_line(line))

    for line in open("AliceInWonderLand200.txt"):
        line = line.strip()
        alice_list.extend(split_line(line.upper()))


    def searching(word, wordList):
        first = 0
        last = len(wordList) - 1
        found = False
        while first <= last and not found:
            middle = (first + last)//2
            if wordList[middle] == word:
                found = True
            else:
                if word < wordList[middle]:
                    last = middle - 1
                else:
                    first = middle + 1
        return found


    for word in alice_list:
        searching(word, dictionary_list)

--------- РЕДАКТИРОВАННЫЙ КОД, КОТОРЫЙ РАБОТАЛ ---------- Обновлено несколько вещей, если у кого-то возникла такая же проблема, и использовалось «для слова не в"перепроверить, что выводилось в поиске. 

"""-----Binary Search-----"""
# search for word, if the word is searched higher than list length, print
words = alice_list
for word in alice_list:
        first = 0
        last = len(dictionary_list) - 1
        found = False
        while first <= last and not found:
            middle = (first + last) // 2
            if dictionary_list[middle] == word:
                found = True
            else:
                if word < dictionary_list[middle]:
                    last = middle - 1
                else:
                    first = middle + 1
                if word > dictionary_list[last]:
                    print("NEW:", word)

# checking to make sure words match
for word in alice_list:
    if word not in dictionary_list:
        print(word)

Ответы [ 2 ]

0 голосов
/ 16 декабря 2018

Требуется ли использовать бинарный поиск для этой программы?В Python есть этот удобный оператор, который называется "in".Учитывая элемент в качестве первого операнда и список / набор / словарь / кортеж в качестве второго, он возвращает True, если этот элемент находится в структуре, и false, если его нет.

Примеры: 

1 in [1, 2, 3, 4] -> True
"APPLE" in ["HELLO", "WORLD"] -> False

Таким образом, для вашего случая большая часть сценария может быть упрощена до: 

for word in alice_list:
    if word not in dictionary_list:
        print(word)

Это напечатает каждое слово, отсутствующее в списке словаря.

0 голосов
/ 16 декабря 2018

Ваша функция split_line() возвращает список.Затем вы берете выходные данные функции и добавляете ее в список словарей, что означает, что каждая запись в словаре представляет собой список слов, а не одно слово.Быстро исправить это, чтобы использовать extend вместо append. 

    dictionary_list.extend(split_line(line))

Набор может быть лучшим выбором, чем список здесь, тогда вам не понадобится двоичный поиск.

- РЕДАКТИРОВАТЬ -
Чтобы напечатать слова, которых нет в списке, просто отфильтруйте список на основе того, возвращает ли ваша функция False.Что-то вроде: 

notfound = [word for word in alice_list if not searching(word, dictionary_list)]
...