Python- 需要快速算法，用于删除文件中所有是其他单词派生词的单词。

Question

Python- 需要快速算法，用于删除文件中所有是其他单词派生词的单词。

4

我们有一个名为wordlist的文件，其中包含1,876 KB的按字母顺序排列的单词，所有单词都长于4个字母，并且在每个新的二字构造（ab、ac、ad等）之间包含一个回车符：

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

我希望创建一个只包含与其他较小单词不相关派生词的新文件。例如，单词列表包含以下单词["abuser, abused, abusers, abuse, abuses, etc.]，则创建的新文件应仅保留单词"abuse"，因为它是所有这些单词之间的“最低公共分母”。同样，单词“rodeo”将被删除，因为它包含单词“rode”。

我尝试了以下实现：

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)

但它总是让我的电脑冻结。有什么解决办法吗？

- Parseltongue

5

啮齿动物也将被视为"rode"的衍生物吗？这似乎是一个过于简单的"衍生物"定义。 - Will

1

你有没有看过词干算法？ - tobyodavies

1

如果你在冰块之前加入冰淇淋，结果会与反过来做不同吗？我认为你需要重新考虑你的算法。 - Lasse V. Karlsen

@Will，我看不出那怎么可能对讨论/答案有所贡献，但仍然感谢您的愤世嫉俗。我想不出更好的解释来传达这个陈述：“删除所有包含仅出现在单词前面的较小根词的单词。” - Parseltongue

3个回答

2

一个可能的改进是使用数据库加载单词，避免在RAM中加载完整的输入文件。另一个选项是在读取文件时处理单词，并在不加载所有内容的情况下编写结果。

以下示例将文件视为读取文件时处理，而不是预先加载到内存中。

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来处理文件。这可以得益于文件的字母顺序排序。

- Manuel Salvadores

这不是O(1)的时间复杂度，只是内存复杂度为O(n)。你需要查看每个单词，但只需要查看一次。实际上，像我的代码一样，由于Python会缓存文件读取，所以需要更多的内存。 - aaronasterling

是的，通过复杂度空间我指的是内存。我改变了措辞以避免混淆。 - Manuel Salvadores

再次强调，我不考虑Python缓冲区的读取方式，但如果它基于内存页面大小实现缓存，则仍然具有恒定的内存复杂度。 - Manuel Salvadores

1

另外，file对象没有print方法。我认为你想要的是write。而且你想要以w模式打开第二个文件。之后，它会运行，如果你去掉多余的print语句，它只比我的慢一点点 ;) - aaronasterling

@aaronasterling 谢谢你提供的 'print' 部分 ... ;) ... 感谢反馈 !!!! 我已经更正了答案。 - Manuel Salvadores

1

由于列表已按字母顺序排列，因此这很简单（使用5兆数据需要0.4秒，因此在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:]))

- Kimvais

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aaronasterling · Accepted Answer

我会这样做：

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个单词的corncob列表。它已经够老了，只有1GB的内存。

$ time python words.py

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

它尽可能地使用迭代器以减少内存占用。你可以通过切片行的末尾而不是使用strip来去除换行符，从而提高性能。

另请注意，这依赖于您的输入已经排序且非空。虽然这是先决条件的一部分，但我对此感到不太抱歉;)