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

Question

我这几天一直在尝试把这个JavaScript脚本转换成Python代码。

到目前为止，我的实现（大部分是直接复制，做了一些小修正）是这样的：

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. 当我尝试把一些文本“学习”到一个“markov”类的对象里（比如：a=markov(); a.learn("sdfg");）时，出现了一个错误：“TypeError: unhashable type: 'list'”，这个错误出现在“learn”函数里的“learnPart”函数中的“mem”字典里。

   所以我现在的问题是，为什么会出现这个异常（对于一个列表对象的TypeError，错误地指向了一个字典对象（字典是可以哈希的））呢？

提前感谢任何建议、方向、意见和帮助 :D

Answer 1

我做了一个简化版的代码：

import re
class Brain():
    H = ''
    def learn(self, txt):
        self.H = txt
    def ask(self,ask):
        H=self.H
        ask = re.compile(r"%s(.*)"%(ask),re.I|re.DOTALL)
        m = ask.search(H)
        print m.group(1)

这是执行的结果：

>>> import brain
>>> bob = brain.Brain()
>>> bob.learn('Mary had a little lamb' )
>>> bob.ask('Mary had')
'a little lamb'

我同意这并不完全是一个马尔可夫链算法。但它有几个优点：

i. 你可以像上面那样直接给ask()输入原始文本。

ii. 代码行数更少。

iii. 希望它更容易理解。

Answer 2

复杂的答案

这里的问题是，learnPart 试图把 getInitial 返回的一个列表当作字典的键来用。列表是可变的，也就是说它们的内容可以改变，因此不能被用作字典的键。

你可以试着在 learnPart 中添加这一行：

def learnPart(key, value):
    key = tuple(key) #<-----Try adding this line
    if not mem[key]:
        mem[key] = []
    mem[key] = value
    return mem

但我觉得这并不能解决所有的问题。

简单的答案

网上有很多用 Python 写的马尔可夫链实现。快速在 Github 上搜索一下，发现有 168 个相关项目：https://github.com/search?l=Python&q=markov+chain

Answer 3

这篇文章的作者在这里。很高兴你觉得它有用！我最初实现马尔可夫链的代码其实是用Python写的，所以接下来的内容会专注于如何用更符合Python风格的方式来写。我会展示如何制作一个二阶的马尔可夫链，因为这个比较容易理解，不过你当然可以通过一些修改来做成N阶的。

数据结构

在JavaScript中，主要的数据结构是通用对象和数组（数组是通用对象的扩展）。而在Python中，你有更多的选择，可以更细致地控制数据结构。下面是这两种实现的主要区别：

• 我们链中的一个状态实际上是一个元组——它是一个不可变的、有序的结构，包含固定数量的元素。我们总是需要 n 个元素（在这个例子中，n=2），而且它们的顺序是有意义的。

• 如果我们使用一个 defaultdict 来包装一个列表，操作内存会更简单，这样我们就可以省去“检查一个状态是否存在，然后再做X”的步骤，直接做X就可以了。

所以，我们在顶部加上 from collections import defaultdict，并修改 markov.memory 的定义：

memory = defaultdict(list)

现在我们把 markov.getInitial 改成返回一个元组（记住这解释的是一个二阶链）：

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

（如果你想进一步扩展，可以使用一个很酷的Python技巧：tuple([''] * 2) 会返回相同的东西。你可以用 None 替代空字符串）

稍后我们会修改使用 genInitial 的部分。

生成和迭代

在JavaScript中没有（但在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'

当然，这个概念还有改进和扩展的空间。但如果我直接给你答案，那就没意思了。

希望这在四个月后仍然能帮到你。