devbox
木道寻08
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

NLTK学习笔记(四):自然语言处理的一些算法研究

作者：木道寻08 | 2024-07-31 18:10:02

赞

踩

NLTK学习笔记(四):自然语言处理的一些算法研究

自然语言处理中算法设计有两大部分：分而治之 和 转化 思想。一个是将大问题简化为小问题，另一个是将问题抽象化，向向已知转化。前者的例子：归并排序；后者的例子：判断相邻元素是否相同（与排序）。

这次总结的自然语言中常用的一些基本算法，算是入个门了。

递归

使用递归速度上会受影响，但是便于理解算法深层嵌套对象。而一些函数式编程语言会将尾递归优化为迭代。

如果要计算n个词有多少种组合方式？按照阶乘定义：n! = n*(n-1)*...*1
  1. def func(wordlist):
  2.     length = len(wordlist)
  3.     if length==1:
  4.         return 1
  5.     else: 
  6.         return func(wordlist[1:])*length
如果要寻找word下位词的大小，并且将他们加和。
  1. from nltk.corpus import wordnet as wn
  2.  
  3. def func(s):#s是WordNet里面的对象
  4.     return 1+sum(func(child) for child in s.hyponyms())
  5.  
  6. dog = wn.synset('dog.n.01')
  7. print(func(dog))
构建一个字母查找树

建立一个嵌套的字典结构，每一级的嵌套包含既定前缀的所有单词。而子查找树含有所有可能的后续词。

  1. def WordTree(trie,key,value):
  2.     if key:
  3.         first , rest = key[0],key[1:]
  4.         if first not in trie:
  5.             trie[first] = {}
  6.         WordTree(trie[first],rest,value)
  7.     else:
  8.         trie['value'] = value
  9.  
  10. WordDict = {}
  11. WordTree(WordDict,'cat','cat')
  12. WordTree(WordDict,'dog','dog')
  13. print(WordDict)

贪婪算法:不确定边界自然语言的分割问题(退火算法的非确定性搜索)

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

  1. import nltk
  2. from random import randint
  3.  
  4. #text = 'doyou'
  5. #segs = '01000'
  6.  
  7. def segment(text,segs):#根据segs，返回切割好的词链表
  8.     words = []
  9.     last = 0
  10.     for i in range(len(segs)):
  11.         if segs[i]=='1':#每当遇见1,说明是词分界
  12.             words.append(text[last:i+1])
  13.             last = i+1
  14.     words.append(text[last:])
  15.     return words 
  16.  
  17. def evaluate(text,segs): #计算这种词分界的得分。作为分词质量，得分值越小越好(分的越细和更准确之间的平衡)
  18.     words = segment(text,segs)
  19.     text_size = len(words)
  20.     lexicon_size = len(' '.join(list(set(words))))
  21.     return text_size + lexicon_size
  22.  
  23. ###################################以下是退火算法的非确定性搜索############################################
  24.  
  25. def filp(segs,pos):#在pos位置扰动
  26.     return segs[:pos]+str(1-int(segs[pos]))+segs[pos+1:]
  27.  
  28. def filp_n(segs,n):#扰动n次
  29.     for i in range(n):
  30.         segs = filp(segs,randint(0,len(segs)-1))#随机位置扰动
  31.     return segs
  32.  
  33. def anneal(text,segs,iterations,cooling_rate):
  34.     temperature = float(len(segs))
  35.     while temperature>=0.5:
  36.         best_segs,best = segs,evaluate(text,segs)
  37.         for i in range(iterations):#扰动次数
  38.             guess = filp_n(segs,int(round(temperature)))
  39.             score = evaluate(text,guess)
  40.             if score<best:
  41.                 best ,best_segs = score,guess
  42.         score,segs = best,best_segs
  43.         temperature = temperature/cooling_rate #扰动边界，进行降温
  44.         print( evaluate(text,segs),segment(text,segs))
  45.     print()
  46.     return segs
  47. text = 'doyouseethekittyseethedoggydoyoulikethekittylikethedoggy'
  48. seg =  '0000000000000001000000000010000000000000000100000000000'
  49. anneal(text,seg,5000,1.2)

动态规划

它在自然语言中运用非常广泛。首先他需要一张表，用来将每一次的子结果存放在查找表之中。避免了重复计算子问题！！！

这里我们讨论一个梵文组合旋律的问题。短音节：S，一个长度；长音节：L，两个长度。所以构建长度为2的方式：{SS,L}。

首先用递归的方式编写一下找到任意音节的函数
  1. def func1(n):
  2.     if n==0:
  3.         return [""]
  4.     elif n==1:
  5.         return ["S"]
  6.     else:
  7.         s = ["S" + item for item in func1(n-1)]
  8.         l = ["L" + item for item in func1(n-2)]
  9.         return s+l
  10. print(func1(4))
使用动态规划来实现找到任意音节的函数

之前递归十分占用时间，如果是40个音节，我们需要重复计算632445986次。如果使用动态规划，我们可以把结果存到一个表中，需要时候调用，而不是很坑爹重复计算。

  1. def func2(n):#采用自下而上的动态规划
  2.     lookup = [[""],["S"]]
  3.     for i in range(n-1):
  4.         s = ["S"+ item for item in lookup[i+1]]
  5.         l = ["L" + item for item in lookup[i]]
  6.         lookup.append(s+l)
  7.     return lookup
  8. print(func2(4)[4])
  9. print(func2(4))
  1. def func3(n,lookup={0:[""],1:["S"]}):#采用自上而下的动态规划
  2.     if n not in lookup:
  3.         s = ["S" + item for item in func3(n-1)]
  4.         l = ["L" + item for item in func3(n-2)]
  5.         lookup[n] = s+l
  6.     return lookup[n]#必须返回lookup[n].否则递归的时候会出错
  7. print(func3(4))

对于以上两种方法，自下而上的方法在某些时候会浪费资源，因为，子问题不一定是解决主问题的必要条件。

NLTK自带装饰符:默记

装饰器@memoize 会存储每次函数调用时的结果及参数，那么之后的在调用，就不用重复计算。而我们可以只把精力放在上层逻辑，而不是更关注性能和时间（被解决了）

  1. from nltk import memoize
  2. @memoize
  3. def func4(n):
  4.     if n==0:
  5.         return [""]
  6.     elif n==1:
  7.         return ["S"]
  8.     else:
  9.         s = ["S" + item for item in func4(n-1)]
  10.         l = ["L" + item for item in func4(n-2)]
  11.         return s+l
  12. print(func4(4))

其他的应用

这里主要介绍一下除了上述两种主要算法外，一些小的使用技巧和相关基础概念。

词汇多样性

词汇多样性主要取决于：平均词长（字母个数/每个单词）、平均句长（单词个数/每个句子）和文本中没歌词出现的次数。

  1. from nltk.corpus import gutenberg
  2. for fileid in gutenberg.fileids():
  3.     num_chars = len(gutenberg.raw(fileid))
  4.     num_words = len(gutenberg.words(fileid))
  5.     num_sents = len(gutenberg.sents(fileid))
  6.     num_vocab = len(set(w.lower() for w in gutenberg.words(fileid)))
  7.     print(int(num_chars/num_words),int(num_words/num_sents),int(num_words/num_vocab),'from',fileid)
文体差异性

文体差异性可以体现在很多方面：动词、情态动词、名词等等。这里我们以情态动词为例，来分析常见情态动词的在不同文本的差别。

  1. from nltk.corpus import brown
  2. from nltk import FreqDist,ConditionalFreqDist
  3. cfd = ConditionalFreqDist(( genere,word) for genere in brown.categories() for word in brown.words(categories=genere))
  4. genres=['news','religion','hobbies']
  5. models = ['can','could','will','may','might','must']
  6. cfd.tabulate(conditions = genres,samples=models)
随机语句生成

从《创世纪》中得到所有的双连词，根据概率分布，来判断哪些词最有可能跟在给定词后面。

  1. import nltk
  2. def create_sentence(cfd,word,num=15):
  3.     for i in range(num):
  4.         print(word,end=" ")
  5.         word = cfd[word].max()#查找word最有可能的后缀
  6. text= nltk.corpus.genesis.words("english-kjv.txt")
  7. bigrams = nltk.bigrams(text)
  8. cfd = nltk.ConditionalFreqDist(bigrams)
  9.  
  10. print(create_sentence(cfd,'living'))
词谜问题解决

单词长度>=3,并且一定有r,且只能出现'egivrvonl'中的字母。

  1. puzzle_word = nltk.FreqDist('egivrvonl')
  2. base_word = 'r'
  3. wordlist = nltk.corpus.words.words()
  4. result = [w for w in wordlist if len(w)>=3 and base_word in w and nltk.FreqDist(w)<=puzzle_word]
  5. #通过FreqDist比较法（比较键对应的value），来完成字母只出现一次的要求！！！
  6. print(result)

时间和空间权衡:全文检索系统

除了研究算法，分析内部实现外。构造辅助数据结构，可以显著加快程序执行。

  1. import nltk
  2. def raw(file):
  3.     contents = open(file).read()
  4.     return str(contents)
  5.  
  6. def snippet(doc,term):#查找doc中term的定位
  7.     text = ' '*30+raw(doc)+' '*30
  8.     pos = text.index(term)
  9.     return text[pos-30:pos+30]
  10.  
  11. files = nltk.corpus.movie_reviews.abspaths()
  12. idx = nltk.Index((w,f) for f in files for w in raw(f).split())
  13. #注意nltk.Index格式
  14.  
  15. query = 'tem'
  16. while query!='quit' and query:
  17.     query = input('>>> input the word:')
  18.     if query in idx:
  19.         for doc in idx[query]:
  20.             print(snippet(doc,query))
  21.     else:
  22.         print('Not found')

欢迎进一步交流本博文相关内容：

博客园地址 : http://www.cnblogs.com/AsuraDong/

CSDN地址 : http://blog.csdn.net/asuradong

也可以致信进行交流 : xiaochiyijiu@163.com

欢迎转载 , 但请指明出处  :  )

转载于:https://www.cnblogs.com/AsuraDong/p/6995132.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/木道寻08/article/detail/910116
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号