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

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

到目前为止，我的实现(主要是blindfull 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:不可散列的类型:'列表'”，对于“mem”词典在“learnPart”函数中，“learn”函数的成员。

因此，到目前为止，我的问题是为什么会发生此异常[列表对象的TypeError，错误地引用了字典对象(可哈希)]？

预先感谢您的任何建议，方向，要点，总体帮助:D

最佳答案

写这篇文章的家伙讲话。很高兴您发现它有用!现在，我对Markov链的第一个实现实际上是在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运算符(see this question给出了很好的解释)在js中尚不存在(但至今)，但在Python中确实存在。

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 ('', '')

(我将类名从markov更改为Markov，因为每次类以小写字母开头时，我都会畏缩)。我将其另存为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'): ['']}

准备好开车了吗？我们仍然必须使用此链!

更改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个月后仍然有帮助。