Python利用字典树实现猎词游戏

目录
  • 解决策略
  • 什么是 Trie?
  • 创建 Trie 字典树
  • 单词测试
  • 总结

猎词(word hunt)是一类很常见的游戏,给你一张字母组成的表,然后让你在这些字母中尽可能多的去寻找单词。这类游戏有不同的变体,一类是你可以多次重复使用这些字母(这类游戏叫做猎词),或者你只能使用一次每个字母(这类游戏叫做字母重组)。你组出来的单词越长就得分越高,使用了所有字母就可以获得最高分。

这类游戏对计算机而言是很「容易」去完成的,而且要强调一个相当有用的数据结构叫做 “Trie”。

解决策略

让我们先拿出一个单词「MAINE」

首先要做的决定我们要如何处理这个问题。如果问题是字母重组,那么我们可以尝试所有可能的字母组合,然后看看它们是否是单词。这对字母重组是一个还不错的解决方案,但是对猎词而言就不能给我们多少帮助了,因为字母可以被重用。所以当你可能发现了单词 ”name” 时,你将再不会发现单词 “nine”。显然我们不能尝试穷尽这些字母所有可能的组合,因为我们不知道一个单词可能被重复多少次。因为这个原因,我们退步为搜索一个词典,去看这个词是否可以只由我们拥有的字母组成。当有一个很大的词典时,这可能耗费大量的时间,并且你每次换了一个词时都必须重复这一步。

作为替代,我们需要一个搜索词典的方法,可以快速告诉我们某个单词是否在词典中。这就是预测性文本结构 Trie 字典树的用武之地。

什么是 Trie?

Trie 是一个树数据结构 — 作为原本树节点储存一个与 key 相关联的值的代替 — 这个节点现在储存 key 本身。节点中的值可用于根据遍历次数来为某些叶子节点或概率值分配顺序。

维基百科中一个 Trie 的例子

上面这个 Trie 的例子由 “A”,“to”,“tea”,“ted”,“ten”,“i”,“in” 和 “inn” 生成。一旦一个像这样的 Trie 字典树结构被生成,去判断任何一个单词是否在这个 Trie 字典树中就是 O(n) 复杂度的。如果我在搜索 “ted”,我会消耗 O(1) 去寻找 “t”,然后从 “t” 节点再消耗 O(1) 去寻找 “e”,并且再从 “te” 节点消耗 O(1) 去到 “d”。

面对问题“这一堆字母在不在这个词典中?”,这就是一个「非常」快速的解答方案。我们首先要做的就是构建词典。

在 Python 中,这个步骤很简单。每个节点的样子都应该是一个词典。所以我们需要从一个空词典开始,然后对词典中的每一个单词,逐字母的检查下一个字母是否在我们的 Trie 字典树结构中,如果不在就添进去。现在,这听起来相当耗费时间,在某些方面也的确如此,但是它只需要完成一次。当 Trie 被建好后,你可以直接使用它而无需任何其它开销。

创建 Trie 字典树

我们需要从一个装满所有可能单词的列表开始(网上有很多这类资源),然后我们的词典加载函数可能长下面这样:

def load():
    with open('words.txt') as wordFile:
        wordList = wordFile.read().split()

    trie = {}
    for word in wordList:
        addWordToTrie(trie, word)

    return trie

我们需要一个函数来给 Trie 中添加单词。我们通过快速浏览 Trie 来检查每一个字母,判断我们是否需要添加一个新的 key。因为我们通过 key 来检索 python 中的字典,所以无需在每个节点储存一个 value。这是一个有自己的 key 值的新词典。

def addWordToTrie(trie, word, idx = 0):
    if idx >= len(word):
        return
    if word[idx] not in d:
        d[word[idx]] = {}
    addWordToTrie(d[word[idx]], word, idx+1)

这里有一个简单的想法。我们接收的参数是当前所在位置的 Trie 字典树(注意在这个例子中,Trie 中的所有节点也是一个 Trie),这个单词,以及我们所查看的字母在单词中的索引。

如果索引超过了单词的长度,我们就停止!如果没有超过,我们需要检查是否这个字母已经在这个 Trie 中。如果这个字母不在这个 Trie 的下一层中,那么我们添加一个新的字典在这一层,当前这个字母就是字典的 key。然后,我们递归的调用这个函数,并且传入我们当前字母对应的词典(也就是 Trie),这个单词,以及下一个索引位置。

使用这两个函数,我们就构建了上面展示的 Trie 字典树。但是有一个问题摆在我们面前。我们如何知道我们找到的是一个「单词」,而不是一个真正的单词的前一「部分」呢?例如,在上面这个 Trie 的例子中,我们希望 “in” 可以像 “inn” 一样返回是一个单词,但是并不希望将 “te” 作为一个词典中的单词来返回。

为了完成这一点,当我们完成一个单词时,「必须」在这个节点中储存一个值。来回头重新审视一下我们的 addWordToTrie 函数,如果这个节点表示一个完整的单词,就将 “leaf” 这个 key 设置为 “True”。

def addWordToTrie(d, word, idx):
    if idx >= len(word):
        d['leaf']=True
        return
    if word[idx] not in d:
        d[word[idx]] = {'leaf':False}
    addWordToTrie(d[word[idx]], word, idx+1)

现在,无论何时我们完成一个单词,都要设置当前这个词典节点的 “leaf” 值为 True,或者我们添加一个新的节点,它的 “leaf” 值为 “False”。

当我们加载这个函数初始化时,应该是同样的设置 {‘leaf’:False},所以我们就无需再拿一个空的字符串来作为有效词的返回。

就是这样!我们已经创建了我们的 Trie 结构,接下来啥时候使用它了。

单词测试

找一个办法来进行尝试:从一个空的列表开始。对我们单词中的每个字母,检查我们的 Trie 字典树,看它是否在其中。如果在,就拿到这个词典子树再重新开始(这样我们可以检查重复的字母)。保持这样进行下去,直到我们找到一个 leaf 标志位为 true 的节点,或者我们在下一层的词典子树中找不到单词中的任何字母。如果我们发现了一个标记为 leaf 的节点,就把这个单词添到列表中。如果我们没有找到下一个词典子树,就返回并执行下一个字母。

def findWords(trie, word, currentWord):
    myWords = [];
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if (trie[letter]['leaf']):
                myWords.append(newWord)
            myWords.extend(findWords(trie[letter], word, newWord))
    return myWords

这里注意一下,我们正在构建一个新单词传递到列表中,但是我们也会递归的去寻找新的单词,用来扩展我们的列表。

有的读者可能已经发现了接下来的问题。如果字母重复怎么办呢?例如我们的单词是 “「TEEN」”,并且我们现在在 “TE” 节点上,我们已经在子树上检查了 “t“,这很好,然后我们在子树上检查 ”e“ 并发现 ”tee“ 是一个单词。我们将 ”tee“ 添加到列表中。但是单词的下一个字母又是 ”e“,所以我们再次找到了 ”tee“。有一些方法去解决这个问题,但是最简单的方法之一就是用集合代替列表。

def findWords(trie, word, currentWord):
    myWords = set()
    for letter in word:
        if letter in trie:
            newWord = currentWord + letter
            if trie[letter]['leaf']:
                myWords.add(newWord)
            myWords = myWords.union(findWords(trie[letter], word, newWord))
    return myWords
 

现在无论我们把同一个单词找到多少次,我们都可以保证列表中的唯一性。我们也可以将输入单词中的字母去重,进而节约处理时间。

就这样!利用这三个函数就可以通过我们输入的字母来找到所有可能在字典中的单词。来让我们把这些包到一个 main 函数里面,然后给一个输入,具体步骤我们已经完成了。

def main():
    print('Loading dictionary...')
    wordTrie = load()
    print('Done\n')

    word = raw_input("What letters should we use: ")
    minLength = int(raw_input("What is the minimum word length: "))
    print("")

    count = 0;
    for word in sorted(findWords(wordTrie, word, "")):
        if len(word) >= minLength:
            count = count+1
            print(word)
    print(str(count) + " words found.")

因为我们不是单词重组,所以我们找到了「太」多单词。使用上面提到的例子「MAINE」和一个我找到的词典 — 大约有 370000 个单词 — 这个程度发现了 208 个单词。这也是为什么我添加了一个最短单词长度的原因。限制单词长度至少为七,我们可以得到如下结果:

Loading dictionary…
 
Done
 
What letters should we use: maine
 
What is the minimum word length: 7
 
amninia
 
anaemia
 
anamnia
 
animine
 
emmenia
 
enamine
 
manienie
 
mannaia
 
meminna
 
miminae
 
minaean
 
11 words found.

加载词典消耗了大约半秒,后面的查找单词基本上感受不到明显的时间消耗。

为了一个单词去每次都重新建树是很低效的,所以最好可以重用它,要么是保存整个数据结构,要么尝试一次循环的查找多个单词。

总结

但愿这篇文章可以为你提供一个 Trie 的基本介绍,便于你去解决一些单词问题。当你想要一些自动补充完成的任务时,Trie 是一个很好用的数据结构。短信,搜索甚至是指引方向,都可以使用系统中的数据构建 Trie 来帮助预测用户下一步想要输入什么。正如我们所看到的,它也是在一个搜索大量的现有路径时很好的结构,在这个例子中,这个路径就是有效的单词。

以上就是Python利用字典树实现猎词游戏的详细内容,更多关于Python字典树的资料请关注我们其它相关文章!

(0)

相关推荐

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

  • Python实现简单字典树的方法

    本文实例讲述了Python实现简单字典树的方法.分享给大家供大家参考,具体如下: #coding=utf8 """代码实现了最简单的字典树,只支持由小写字母组成的字符串. 在此代码基础上扩展一下,就可以实现比较复杂的字典树,比如带统计数的,或支持更多字符的字典树, 或者是支持删除等操作. """ class TrieNode(object): def __init__(self): # 是否构成一个完成的单词 self.is_word = Fal

  • python自然语言处理之字典树知识总结

    一.什么是字典树 在自然语言处理中,字符串集合常用字典树存储,这是一种字符串上的树形数据结构.字典树中每条边都对应一个字,从根节点往下的路径构成一个个字符串. 字典树并不直接在节点上存储字符串,而是将词语视作根节点到某节点之间的一条路径,并在终点节点上做个标记(表明到该节点就结束了). 要查询一个单词,指需要顺着这条路径从根节点往下走.如果能走到标记的节点,则说明该字符串在集合中,否则说明不在.下图为字典树结构示例: 如上图所示,每条路径都是一个词汇,且没有子节点就可以判定该条路径结尾了.具体可

  • 详解字典树Trie结构及其Python代码实现

    字典树(Trie)可以保存一些字符串->值的对应关系.基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串. Trie 的强大之处就在于它的时间复杂度.它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关.Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题:Trie 的缺点是空间消耗很高. 至于Trie树的实现

  • Python利用字典树实现猎词游戏

    目录 解决策略 什么是 Trie? 创建 Trie 字典树 单词测试 总结 猎词(word hunt)是一类很常见的游戏,给你一张字母组成的表,然后让你在这些字母中尽可能多的去寻找单词.这类游戏有不同的变体,一类是你可以多次重复使用这些字母(这类游戏叫做猎词),或者你只能使用一次每个字母(这类游戏叫做字母重组).你组出来的单词越长就得分越高,使用了所有字母就可以获得最高分. 这类游戏对计算机而言是很「容易」去完成的,而且要强调一个相当有用的数据结构叫做 “Trie”. 解决策略 让我们先拿出一个

  • Python利用字典将两个通讯录文本合并为一个文本实例

    本文实例主要实现的是利用字典将两个通讯录文本合并为一个文本,具体代码如下: def main(): ftele1=open("d:\TeleAddressBook.txt","rb") ftele2=open("d:\EmailAddressBook.txt","rb") ftele1.readline()#跳过第一行 ftele2.readline() lines1=ftele1.readlines() lines2=fte

  • Python利用字典和列表实现学生信息管理系统

    本文将利用Python中的字典和列表实现学生信息管理系统 文件的存放格式采用的是python自带的pickle模块,需要新建course.txt和student.txt供程序读写. 下面是示例代码 import pickle # 从文件中读取学生信息并返回 def readStudent(): with open("student.txt",'rb') as f: try: return pickle.load(f) #读取失败,说明读取的文件为空,返回空列表即可 except EOF

  • Python利用3D引擎写一个Pong游戏

    目录 前言 实现方法 完整代码 前言 之前,我们用pygame做了一个2D的Pong游戏,今天我们做一个3D的,游戏画面如下: 用ad和←→操作,双人对战 实现该效果我们使用Python强大的3D引擎Ursina,基础的使用方法见这篇文章:详解Python 3D引擎Ursina如何绘制立体图形 接下来开始写代码吧! 实现方法 首先,导入ursina和随机库 from ursina import * import random as rd 定义两个玩家的分数 scorea=scoreb=0 然后,

  • Python利用字典破解WIFI密码的方法

    最近看到网上的一些作品,然后进行一些完善.只是用于学习,不要去干坏事哦.程序来源于网,我只是做了一些优化.当然这种方法破解还是有点慢哦.我用的python 3.6.5 既然要破解wifi,那么连接wifi的模块首先要有的,我们要导入pywifi模块. 有些同学可能没有这个,如果直接通过pip安装的话,可能不能用,听说这个wifi模块被停用了,所以大家如果通过pip安装的不行,那么就下载我提供的. 链接:https://pan.baidu.com/s/1rn-5F1CS5UXOTcLh3QAMhg

  • Python学习小技巧之利用字典的默认行为

    本文介绍的是关于Python利用字典的默认行为的相关内容,分享出来供大家参考学习,下面来看看详细的介绍: 典型代码1: from collections import defaultdict if __name__ == '__main__': data = defaultdict(int) data[0] += 1 print(data) 输出1: defaultdict(<type 'int'>, {0: 1}) 典型代码2: if __name__ == '__main__': data

  • C#实现前向最大匹、字典树(分词、检索)的示例代码

    场景:现在有一个错词库,维护的是错词和正确词对应关系.比如:错词"我门"对应的正确词"我们".然后在用户输入的文字进行错词校验,需要判断输入的文字是否有错词,并找出错词以便提醒用户,并且可以显示出正确词以便用户确认,如果是错词就进行替换. 首先想到的就是取出错词List放在内存中,当用户输入完成后用错词List来foreach每个错词,然后查找输入的字符串中是否包含错词.这是一种有效的方法,并且能够实现.问题是错词的数量比较多,目前有10多万条,将来也会不断更新扩展

  • 利用Python爬取微博数据生成词云图片实例代码

    前言 在很早之前写过一篇怎么利用微博数据制作词云图片出来,之前的写得不完整,而且只能使用自己的数据,现在重新整理了一下,任何的微博数据都可以制作出来,一年一度的虐汪节,是继续蹲在角落默默吃狗粮还是主动出击告别单身汪加入散狗粮的行列就看你啦,七夕送什么才有心意,程序猿可以试试用一种特别的方式来表达你对女神的心意.有一个创意是把她过往发的微博整理后用词云展示出来.本文教你怎么用Python快速创建出有心意词云,即使是Python小白也能分分钟做出来.下面话不多说了,来一起看看详细的介绍吧. 准备工作

  • 利用Python编写简易版德州扑克小游戏

    目录 德州扑克简要介绍 什么是德州扑克 游戏规则简要介绍 德州扑克游戏的python实现过程 游戏初始化 评选赢家 游戏主题函数 游戏体验与展示 模块不足与后续改进 德州扑克简要介绍 什么是德州扑克 德州扑克不知道大家是否玩过,它是起源于美国的得克萨斯州的一种博弈类卡牌游戏,英文名叫做Texas Hold’em Poker.玩法上又分为常规桌(Cash, 现金局),单桌赛(SNG)和多桌锦标赛(MTT).虽然扑克种类繁多,但基本的扑克规则通常保持一致.它是一种考验心态与谋略的游戏. 游戏规则简要

随机推荐