javascript - 将文本预测脚本 [Markov Chain] 从 javascript 转换为 python

Question

最近几天我一直在尝试转换 this js script到 python 代码。

到目前为止，我的实现(主要是盲目的 cp，一些小修复):

import random
class markov:
    memory = {}
    separator = ' '
    order = 2

    def getInitial(self):
        ret = []
        for i in range(0, self.order, 1):
            ret.append('')
        return ret

    def breakText(self, txt, cb):
        parts = txt.split(self.separator)
        prev = self.getInitial()
        def step(self):
            cb(prev, self.next)
            prev.shift()#Javascript function.
            prev.append(self.next)
        #parts.forEach(step) # - step is the function above.
        cb(prev, '')

    def learn(self, txt):
        mem = self.memory
        def learnPart(key, value):
            if not mem[key]:
                mem[key] = []
            mem[key] = value
            return mem
        self.breakText(txt, learnPart)

    def step(self, state, ret):
        nextAvailable = self.memory[state] or ['']
        self.next = nextAvailable[random.choice(nextAvailable.keys())]
        if not self.next:
            return ret
        ret.append(next)
        nextState = state.slice(1)
        return self.step(nextState, ret)

    def ask(self, seed):
        if not seed:
            seed = self.genInitial()
        seed = seed + self.step(seed, []).join(self.separator)
        return seed

问题:

我完全不了解javascript。

当我尝试向“markov”类对象“学习”一些文本时[例如:a=markov(); a.learn("sdfg");] 我收到以下错误:“TypeError: unhashable type: 'list'”，对于“learnPart”函数中的“mem”字典，“learn”函数的成员。

所以到目前为止我的问题是为什么会出现这个异常 [TypeError for a list object, falsely refer to a dictionary object (which is hashable)]？

在此先感谢您的任何建议、方向、要点和帮助:D

Answer 1

写这篇文章的人说话。很高兴你发现它有用!现在，我的马尔可夫链的第一个实现实际上是在 Python 中，所以这个答案将集中在如何以更 Pythonic 的方式编写它。我将展示如何制作一个 2 阶马尔可夫链，因为它们很容易讨论，但您当然可以通过一些修改使其成为 N 阶。

数据结构

在 js 中，两个突出的数据结构是泛型对象和数组(它是泛型对象的扩展)。然而，在 Python 中，您还有其他选项可以进行更细粒度的控制。以下是两种实现的主要区别:

我们链中的状态实际上是一个元组 - 一个不可变的有序结构，具有固定数量的元素。我们一直想要n元素(在本例中为 n=2 )并且它们的顺序是有意义的。

如果我们使用 defaultdict 来操作内存会更容易。包装一个列表，因此我们可以跳过“检查状态是否不存在，然后执行 X”，而直接执行 X。

所以，我们贴一个 from collections import defaultdict在顶部并更改方式 markov.memory被定义为:

memory = defaultdict(list)

现在我们更改 markov.getInitial返回一个元组(记住这解释了一个 order-2 链):

def getInitial(self):
    return ('', '')

(如果你想进一步扩展它，你可以使用一个非常简洁的 Python 技巧: tuple([''] * 2) 将返回相同的东西。你可以使用 None 而不是空字符串)

我们将着手改变 genInitial 的用途。一会儿。

产量和迭代
yield 是 js 中不存在但在 Python 中确实存在的一个强大概念。运算符( see this question 有很好的解释)。

Python 的另一个特性是它的通用 for环形。你几乎可以很容易地检查任何东西，包括生成器(使用 yield 的函数)。将两者结合起来，我们可以重新定义 breakText :

def breakText(self, txt):
    #our very own (ε,ε)
    prev = self.getInitial()

    for word in txt.split(self.separator):
        yield prev, word
        #will be explained in the next paragraph
        prev = (prev[1], word)

    #end-of-sentence, prev->ε
    yield prev, ''

上面的神奇部分， prev = (prev[1], word)可以通过示例进行最好的解释:

>>> a = (0, 1)
>>> a
(0, 1)
>>> a = (a[1], 2)
>>> a
(1, 2)

这就是我们在单词列表中前进的方式。现在我们转到使用 breakText 的内容。 , 对 markov.learn 的重新定义:

def learn(self, txt):
    for part in self.breakText(txt):
        key = part[0]
        value = part[1]

        self.memory[key].append(value)

因为我们的内存是 defaultdict ，我们不必担心 key 不存在。

在路边小便

好的，我们已经实现了一半的链条，是时候看看它的实际效果了!到目前为止我们有什么:

from collections import defaultdict

class Markov:
    memory = defaultdict(list)
    separator = ' '

    def learn(self, txt):
        for part in self.breakText(txt):
            key = part[0]
            value = part[1]

            self.memory[key].append(value)

    def breakText(self, txt):
        #our very own (ε,ε)
        prev = self.getInitial()

        for word in txt.split(self.separator):
            yield prev, word
            prev = (prev[1], word)

        #end-of-sentence, prev->ε
        yield (prev, '')

    def getInitial(self):
        return ('', '')

(我将类(class)名称从 markov 更改为 Markov，因为每次类(class)以小写字母开头时我都会畏缩)。我将其保存为 brain.py并加载了 Python。

>>> import brain
>>> bob = brain.Markov()
>>> bob.learn('Mary had a little lamb')
>>> bob.memory
defaultdict(<class 'list'>, {('had', 'a'): ['little'], ('Mary', 'had'): ['a'], ('', ''): ['Mary'], ('little', 'lamb'): [''], ('a', 'little'): ['lamb'], ('', 'Mary'): ['had']})

成功!让我们更仔细地看一下结果，看看我们做对了:

{ ('', ''): ['Mary'],
  ('', 'Mary'): ['had'],
  ('Mary', 'had'): ['a'],
  ('a', 'little'): ['lamb'],
  ('had', 'a'): ['little'],
  ('little', 'lamb'): ['']}

拉上 zipper 准备好开车了吗？我们还是得用这个链子!

更改 step功能

我们已经满足了重制 step 所需的条件.我们有defaultdict，所以我们可以使用 random.choice马上，我可以作弊一点，因为我知道链条的顺序。我们也可以摆脱递归(有些遗憾)，如果我们将其视为一个通过链单步执行的函数(我在原始文章中的错误 - 一个命名错误的函数)。

def step(self, state):
    choice = random.choice(self.memory[state] or [''])

    if not choice:
        return None

    nextState = (state[1], choice)
    return choice, nextState

我很遗憾地添加了 or ['']因为 random.choice提示空列表。最后，我们将大部分逻辑移至 ask。 (句子的实际结构):

def ask(self, seed=False):
    ret = []

    if not seed:
        seed = self.getInitial()

    while True:
        link = self.step(seed)

        if link is None:
            break

        ret.append(link[0])
        seed = link[1]

    return self.separator.join(ret)

是的，有点恶心。我们可以给 step一个更好的名字，并把它变成了发电机，但我和怀孕的妻子会面要迟到了，她即将生下一个婴儿，他把炉子放在我被拖走的车里着火了!我最好快点!

大结局

但首先，与鲍勃交谈:

from collections import defaultdict
import random

class Markov:
    memory = defaultdict(list)
    separator = ' '

    def learn(self, txt):
        for part in self.breakText(txt):
            key = part[0]
            value = part[1]

            self.memory[key].append(value)

    def ask(self, seed=False):
        ret = []

        if not seed:
            seed = self.getInitial()

        while True:
            link = self.step(seed)

            if link is None:
                break

            ret.append(link[0])
            seed = link[1]

        return self.separator.join(ret)

    def breakText(self, txt):
        #our very own (ε,ε)
        prev = self.getInitial()

        for word in txt.split(self.separator):
            yield prev, word
            prev = (prev[1], word)

        #end-of-sentence, prev->ε
        yield (prev, '')

    def step(self, state):
        choice = random.choice(self.memory[state] or [''])

        if not choice:
            return None

        nextState = (state[1], choice)
        return choice, nextState

    def getInitial(self):
        return ('', '')

并加载它:

>>> import brain
>>> bob = brain.Markov()
>>> bob.learn('Mary had a little lamb')
>>> bob.ask()
'Mary had a little lamb'
>>> bob.learn('Mary had a giant crab')
>>> bob.ask(('Mary', 'had'))
'a giant crab'

当然，这个概念还有改进和扩展的空间。但是，如果我只是给您答案，那将没有任何乐趣。

希望这在 4 个月后仍然会有所帮助。