Python - нужен быстрый алгоритм, который удаляет все слова в файле, которые являются производными другими словами

Question

У нас есть файл с именем wordlist, который содержит алфавитные слова объемом 1876 КБ, все из которых длиннее 4 букв и содержат один возврат каретки между каждой новой двухбуквенной конструкцией (ab, ac, ad и т. Д., Слова все содержат возвраты между ними):

 wfile = open("wordlist.txt", "r+")

Я хочу создать новый файл, который содержит только слова, которые не являются производными от других, меньших слов. Например, список слов содержит следующие слова [«оскорбитель, оскорбление, оскорбление, оскорбление, оскорбление и т. Д.]. В созданном новом файле должно сохраняться только слово« оскорбление », поскольку это« самый низкий общий знаменатель »(если будет) между всеми этими словами. Аналогично, слово "родео" будет удалено, потому что оно содержит слово роде.

Я попробовал эту реализацию:

def root_words(wordlist):
    result = []
    base = wordlist[1]
    for word in wordlist:
        if not word.startswith(base):
            result.append(base)
            print base
            base=word
    result.append(base)
    return result;


def main():
    wordlist = []
    wfile = open("wordlist.txt", "r+")

    for line in wfile:
        wordlist.append(line[:-1])

    wordlist = root_words(wordlist)
    newfile = open("newwordlist.txt", "r+")    
    newfile.write(wordlist)

Но это всегда замораживало мой компьютер. Любые решения?

Answer 1

Я бы сделал что-то вроде этого:

def bases(words):
    base = next(words)
    yield base
    for word in words:
        if word and not word.startswith(base):
            yield word
            base = word


def get_bases(infile, outfile):
    with open(infile) as f_in:
        words = (line.strip() for line in f_in)
        with open(outfile, 'w') as f_out:
            f_out.writelines(word + '\n' for word in bases(words))

Это идет по списку кукурузного початка из 58 000 слов за одну пятую секунды на моем довольно старом ноутбуке. Он достаточно стар, чтобы иметь один гигабайт памяти.

$ time python words.py

real        0m0.233s
user        0m0.180s
sys         0m0.012s

Он использует итераторы повсюду, чтобы облегчить работу с памятью. Вероятно, вы могли бы повысить производительность, отрезав конец строки вместо использования полосы, чтобы избавиться от перевода строки.

Также обратите внимание, что это зависит от того, как ваш ввод сортируется и не является пустым. Это было частью заявленных предварительных условий, поэтому я не чувствую, что слишком плохо об этом;)

Answer 2

Одним из возможных улучшений является использование базы данных для загрузки слов и избегания загрузки полного входного файла в ОЗУ.Другой вариант - обработать слова, когда вы читаете их из файла, и записать результаты, не загружая все данные в память.

В следующем примере файл обрабатывается как прочитанный без предварительной загрузки содержимого в память.

def root_words(f,out):
    result = []
    base = f.readline()
    for word in f:
        if not word.startswith(base):
            out.write(base + "\n")
            base=word
    out.write(base + "\n")

def main():
    wfile = open("wordlist.txt", "r+")
    newfile = open("newwordlist.txt", "w")
    root_words(wfile,newfile)
    wfile.close()
    newfile.close()

Сложность памяти в этом решении составляет O (1), поскольку переменная base - единственное, что вам нужно для обработки файла.Это можно сделать благодаря тому, что файл отсортирован по алфавиту.

Answer 3

, так как список в алфавитном порядке, это делает трюк (занимает 0,4 секунды с 5 мегабайтами данных, поэтому не должно быть проблем с 1,8)

res = [" "]

with open("wordlist.txt","r") as f:
    for line in f:
        tmp = line.strip()
        if tmp.startswith(res[-1]):
            pass
        else:
            res.append(tmp)

with open("newlist.txt","w") as f:
    f.write('\n'.join(res[1:]))