将文本预测脚本[马尔可夫链]从javascript转换为python

Question

我一直在尝试将这个js脚本转换为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

问题:

1. 我完全不了解javascript.

2. 当我试图"学习"一些文本到"马尔可夫"类对象[例如:a = markov(); a.learn("sdfg");]我得到以下错误:"TypeError:unhashable type:'list'",用于"learnPart"函数中的"mem"字典,"learn"函数的成员.

   所以到目前为止我的问题是为什么会发生这种异常[列表对象的TypeError,错误地引用字典对象(可以清除)]？

提前感谢任何建议,方向,要点,一般帮助:D

Answer 1

写这篇文章的家伙说.很高兴你发现它很有用!现在,我第一次实现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.

产量和迭代

在js中尚未存在但在Python中确实存在的强大概念是yield运算符(请参阅此问题以获得很好的解释).

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,我们不必担心密钥不存在.

在路边的小便休息

好的,我们已经实施了一半的链条,有时间看到它在行动!到目前为止我们有什么:

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一个更好的名字,并把它变成一个发电机,但是我和我怀孕的妻子会面的时间已经很晚了,她正准备生一个孩子,这个孩子在我的被拖走的汽车里着火了!我好快点!

盛大的结局

但首先,与bob谈话:

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个月后这仍然有用.