如何加速这个词元组查找算法？

Question

我正在尝试创建一个简单的模型来预测句子中的下一个单词。我有一个很大的 .txt 文件，其中包含由“\n”分隔的句子。我还有一个词汇表文件，其中列出了我的 .txt 文件中的每个唯一单词和一个唯一 ID。我使用词汇文件将语料库中的单词转换为相应的 ID。现在我想做一个简单的模型，它从 txt 文件中读取 ID 并找到单词对以及这些单词对在语料库中出现了多少次。我已经成功编写了以下代码：

tuples = [[]] #array for word tuples to be stored in
data = []   #array for tuple frequencies to be stored in

data.append(0) #tuples array starts with an empty element at the beginning for some reason.
            # Adding zero to the beginning of the frequency array levels the indexes of the two arrays

with open("markovData.txt") as f:
    contentData = f.readlines()
    contentData = [x.strip() for x in contentData]
    lineIndex = 0
    for line in contentData:
        tmpArray = line.split() #split line to array of words
        tupleIndex = 0
        tmpArrayIndex = 0
        for tmpArrayIndex in range(len(tmpArray) - 1): #do this for every word except the last one since the last word has no word after it.
            if [tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]] in tuples: #if the word pair is was seen before
                data[tuples.index([tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]])] += 1 #increment the frequency of said pair
            else:
                tuples.append([tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]]) #if the word pair is never seen before
                data.append(1)                                                        #add the pair to list and set frequency to 1.

        #print every 1000th line to check the progress
        lineIndex += 1
        if ((lineIndex % 1000) == 0):
            print(lineIndex)

with open("markovWindowSize1.txt", 'a', encoding="utf8") as markovWindowSize1File:
    #write tuples to txt file
    for tuple in tuples:
        if (len(tuple) > 0): # if tuple is not epmty
            markovWindowSize1File.write(str(element[0]) + "," + str(element[1]) + " ")

    markovWindowSize1File.write("\n")
    markovWindowSize1File.write("\n")
    #blank spaces between two data

    #write frequencies of the tuples to txt file
    for element in data:
        markovWindowSize1File.write(str(element) + " ")

    markovWindowSize1File.write("\n")
    markovWindowSize1File.write("\n")

此代码的前几千行似乎运行良好。然后事情开始变慢，因为元组列表不断变大，我必须搜索整个元组列表以检查之前是否看到过下一个单词对。我设法在 30 分钟内获得了 50k 行的数据，但我有更大的语料库，有数百万行。有没有一种方法可以更有效地存储和搜索单词对？矩阵可能会工作得更快，但我的唯一字数约为 300.000 字。这意味着我必须创建一个以整数作为数据类型的 300k*300k 矩阵。即使在利用了对称矩阵之后，它也需要很多比我拥有的更多的内存。

我尝试使用 numpy 中的 memmap 将矩阵存储在磁盘而不是内存中，但它需要大约 500 GB 的可用磁盘space。

然后我研究了稀疏矩阵，发现我可以只存储非零值及其对应的行和列号。这就是我在代码中所做的。

现在，这个模型可以工作，但它在正确猜测下一个单词方面非常糟糕（大约 8% 的成功率）。我需要用更大的语料库进行训练以获得更好的结果。我该怎么做才能使这个词对查找代码更有效率？

谢谢。

编辑：感谢大家的回答，我现在可以在大约 15 秒内处理约 50 万行的语料库。我正在为有类似问题的人添加下面代码的最终版本：

import numpy as np
import time

start = time.time()
myDict = {} # empty dict

with open("markovData.txt") as f:
    contentData = f.readlines()
    contentData = [x.strip() for x in contentData]
    lineIndex = 0
    for line in contentData:
        tmpArray = line.split() #split line to array of words
        tmpArrayIndex = 0
        for tmpArrayIndex in range(len(tmpArray) - 1): #do this for every word except the last one since the last word has no word after it.
            if (tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]) in myDict: #if the word pair is was seen before
                myDict[tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]] += 1  #increment the frequency of said pair
        else:
            myDict[tmpArray[tmpArrayIndex], tmpArray[tmpArrayIndex + 1]] = 1 #if the word pair is never seen before
                                                                              #add the pair to list and set frequency to 1.

    #print every 1000th line to check the progress
    lineIndex += 1
    if ((lineIndex % 1000) == 0):
        print(lineIndex)


end = time.time()
print(end - start)

keyText= ""
valueText = ""

for key1,key2 in myDict:
    keyText += (str(key1) + "," + str(key2) + " ")
    valueText += (str(myDict[key1,key2]) + " ")


with open("markovPairs.txt", 'a', encoding="utf8") as markovPairsFile:
    markovPairsFile.write(keyText)

with open("markovFrequency.txt", 'a', encoding="utf8") as markovFrequencyFile:
    markovFrequencyFile.write(valueText)

Answer 1

据我了解，您正在尝试使用 n-grams 的频率（长度为 n 的单词元组）构建隐马尔可夫模型。也许只是尝试一种更有效的可搜索数据结构，例如嵌套字典。它可以是

的形式

{ID_word1:{ID_word1:x1,... ID_wordk:y1}, ...ID_wordk:{ID_word1:xn, ...ID_wordk:yn}}.

这意味着您只有 k**2 个字典条目用于 2 个单词的元组（google 最多使用 5 个进行自动翻译），其中 k 是 V 的基数，您的（有限）词汇表.这应该会提高您的性能，因为您不必搜索不断增长的元组列表。 x 和 y 代表出现次数，遇到元组时应增加出现次数。（永远不要使用 in-built 函数 count()！）

Answer 2

我还会研究 collections.Counter，一种专为您的任务设计的数据结构。 Counter 对象就像一本字典，但会计算键条目的出现次数。您可以通过在遇到它时简单地增加一个词对来使用它：

from collections import Counter

word_counts = Counter()
with open("markovData.txt", "r") as f:
    # iterate over word pairs
    word_counts[(word1, word2)] += 1

或者，您可以按照现有的方式构造元组列表，然后将其作为对象简单地传递到计数器中，以计算末尾的频率：

word_counts = Counter(word_tuple_list)

如何加速这个词元组查找算法？

How to speed up this word-tuple finding algorithm?

python

performance

nlp

processing-efficiency