import?jieba?
'''''?
Created?on?2015-11-23?
'''?
def?word_split(text):?
"""?
Split?a?text?in?words.?Returns?a?list?of?tuple?that?contains?
(word,?location)?location?is?the?starting?byte?position?of?the?word.?
"""?
word_list?=?[]?
windex?=?0?
word_primitive?=?jieba.cut(text,?cut_all?=?True)?
for?word?in?word_primitive:?
if?len(word)?>?0:?
word_list.append((windex,?word))?
windex?+=?1?
return?word_list?
def?inverted_index(text):?
"""?
Create?an?Inverted-Index?of?the?specified?text?document.?
{word:[locations]}?
"""?
inverted?=?{}?
for?index,?word?in?word_split(text):?
locations?=?inverted.setdefault(word,?[])?
locations.append(index)?
return?inverted?
def?inverted_index_add(inverted,?doc_id,?doc_index):?
"""?
Add?Invertd-Index?doc_index?of?the?document?doc_id?to?the?
Multi-Document?Inverted-Index?(inverted),?
using?doc_id?as?document?identifier.?
{word:{doc_id:[locations]}}?
"""?
for?word,?locations?in?doc_index.iteritems():?
indices?=?inverted.setdefault(word,?{})?
indices[doc_id]?=?locations?
return?inverted?
def?search_a_word(inverted,?word):?
"""?
search?one?word?
"""?
word?=?word.decode('utf-8')?
if?word?not?in?inverted:?
return?None?
else:?
word_index?=?inverted[word]?
return?word_index?
def?search_words(inverted,?wordList):?
"""?
search?more?than?one?word?
"""?
wordDic?=?[]?
docRight?=?[]?
for?word?in?wordList:?
if?isinstance(word,?str):?
word?=?word.decode('utf-8')?
if?word?not?in?inverted:?
return?None?
else:?
element?=?inverted[word].keys()?
element.sort()?
wordDic.append(element)?
numbers?=?len(wordDic)?
inerIndex?=?[0?for?i?in?range(numbers)]?
docIndex?=?[wordDic[i][0]?for?i?in?range(numbers)]?
flag?=?True?
while?flag:?
if?min(docIndex)?==?max(docIndex):?
docRight.append(min(docIndex))?
inerIndex?=?[inerIndex[i]+1?for?i?in?range(numbers)]?
for?i?in?range(numbers):?
if?inerIndex[i]?>=?len(wordDic[i]):?
flag?=?False?
return?docRight?
docIndex?=?[wordDic[i][inerIndex[i]]?for?i?in?range(numbers)]?
else:?
minIndex?=?min(docIndex)?
minPosition?=?docIndex.index(minIndex)?
inerIndex[minPosition]?+=?1?
if?inerIndex[minPosition]?>=?len(wordDic[minPosition]):?
flag?=?False?
return?docRight?
docIndex?=?[wordDic[i][inerIndex[i]]?for?i?in?range(numbers)]?
def?search_phrase(inverted,?phrase):?
"""?
search?phrase?
"""?
docRight?=?{}?
temp?=?word_split(phrase)?
wordList?=?[temp[i][1]?for?i?in?range(len(temp))]?
docPossible?=?search_words(inverted,?wordList)?
for?doc?in?docPossible:?
wordIndex?=?[]?
indexRight?=?[]?
for?word?in?wordList:?
wordIndex.append(inverted[word][doc])?
numbers?=?len(wordList)?
inerIndex?=?[0?for?i?in?range(numbers)]?
words?=?[wordIndex[i][0]?for?i?in?range(numbers)]?
flag?=?True?
while?flag:?
if?words[-1]?-?words[0]?==?numbers?-?1:?
indexRight.append(words[0])?
inerIndex?=?[inerIndex[i]+1?for?i?in?range(numbers)]?
for?i?in?range(numbers):?
if?inerIndex[i]?>=?len(wordIndex[i]):?
flag?=?False?
docRight[doc]?=?indexRight?
break?
if?flag:?
words?=?[wordIndex[i][inerIndex[i]]?for?i?in?range(numbers)]?
else:?
minIndex?=?min(words)?
minPosition?=?words.index(minIndex)?
inerIndex[minPosition]?+=?1?
if?inerIndex[minPosition]?>=?len(wordIndex[minPosition]):?
flag?=?False?
break?
if?flag:?
words?=?[wordIndex[i][inerIndex[i]]?for?i?in?range(numbers)]?
return?docRight?
if?__name__?==?'__main__':?
doc1?=?"""?
中文分詞指的是將壹個漢字序列切分成壹個壹個單獨的詞。分詞就是將連續的字序列按照壹定的規範?
重新組合成詞序列的過程。我們知道，在英文的行文中，單詞之間是以空格作為自然分界符的，而中文?
只是字、句和段能通過明顯的分界符來簡單劃界，唯獨詞沒有壹個形式上的分界符，雖然英文也同樣?
存在短語的劃分問題，不過在詞這壹層上，中文比之英文要復雜的多、困難的多。?
"""?
doc2?=?"""?
存在中文分詞技術，是由於中文在基本文法上有其特殊性，具體表現在：?
與英文為代表的拉丁語系語言相比，英文以空格作為天然的分隔符，而中文由於繼承自古代漢語的傳統，?
詞語之間沒有分隔。 古代漢語中除了連綿詞和人名地名等，詞通常就是單個漢字，所以當時沒有分詞?
書寫的必要。而現代漢語中雙字或多字詞居多，壹個字不再等同於壹個詞。?
在中文裏，“詞”和“詞組”邊界模糊?
現代漢語的基本表達單元雖然為“詞”，且以雙字或者多字詞居多，但由於人們認識水平的不同，對詞和?
短語的邊界很難去區分。?
例如：“對隨地吐痰者給予處罰”，“隨地吐痰者”本身是壹個詞還是壹個短語，不同的人會有不同的標準，?
同樣的“海上”“酒廠”等等，即使是同壹個人也可能做出不同判斷，如果漢語真的要分詞書寫，必然會出現?
混亂，難度很大。?
中文分詞的方法其實不局限於中文應用，也被應用到英文處理，如手寫識別，單詞之間的空格就不很清楚，?
中文分詞方法可以幫助判別英文單詞的邊界。?
"""?
doc3?=?"""?
作用?
中文分詞是文本挖掘的基礎，對於輸入的壹段中文，成功的進行中文分詞，可以達到電腦自動識別語句含義的效果。?
中文分詞技術屬於自然語言處理技術範疇，對於壹句話，人可以通過自己的知識來明白哪些是詞，哪些不是詞，?
但如何讓計算機也能理解？其處理過程就是分詞算法。?
影響?
中文分詞對於搜索引擎來說，最重要的並不是找到所有結果，因為在上百億的網頁中找到所有結果沒有太多的意義，?
沒有人能看得完，最重要的是把最相關的結果排在最前面，這也稱為相關度排序。中文分詞的準確與否，常常直接?
影響到對搜索結果的相關度排序。從定性分析來說，搜索引擎的分詞算法不同，詞庫的不同都會影響頁面的返回結果?
"""?
doc4?=?"""?
這種方法又叫做機械分詞方法，它是按照壹定的策略將待分析的漢字串與壹個“充分大的”機器詞典中的詞條進行配，?
若在詞典中找到某個字符串，則匹配成功（識別出壹個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向?
匹配和逆向匹配；按照不同長度優先匹配的情況，可以分為最大（最長）匹配和最小（最短）匹配；常用的幾種?
機械分詞方法如下：?
正向最大匹配法（由左到右的方向）；?
逆向最大匹配法（由右到左的方向）；?
最少切分（使每壹句中切出的詞數最小）；?
雙向最大匹配法（進行由左到右、由右到左兩次掃描）?
還可以將上述各種方法相互組合，例如，可以將正向最大匹配方法和逆向最大匹配方法結合起來構成雙向匹配法。?
由於漢語單字成詞的特點，正向最小匹配和逆向最小匹配壹般很少使用。壹般說來，逆向匹配的切分精度略高於?
正向匹配，遇到的歧義現象也較少。統計結果表明，單純使用正向最大匹配的錯誤率為，單純使用逆向?
最大匹配的錯誤率為。但這種精度還遠遠不能滿足實際的需要。實際使用的分詞系統，都是把機械分詞?
作為壹種初分手段，還需通過利用各種其它的語言信息來進壹步提高切分的準確率。?
壹種方法是改進掃描方式，稱為特征掃描或標誌切分，優先在待分析字符串中識別和切分出壹些帶有明顯特征?
的詞，以這些詞作為斷點，可將原字符串分為較小的串再來進機械分詞，從而減少匹配的錯誤率。另壹種方法?
是將分詞和詞類標註結合起來，利用豐富的詞類信息對分詞決策提供幫助，並且在標註過程中又反過來對分詞?
結果進行檢驗、調整，從而極大地提高切分的準確率。?
對於機械分詞方法，可以建立壹個壹般的模型，在這方面有專業的學術論文，這裏不做詳細論述。?
"""?
doc5?=?"""?
從形式上看，詞是穩定的字的組合，因此在上下文中，相鄰的字同時出現的次數越多，就越有可能構成壹個詞。?
因此字與字相鄰***現的頻率或概率能夠較好的反映成詞的可信度。可以對語料中相鄰***現的各個字的組合的頻度?
進行統計，計算它們的互現信息。定義兩個字的互現信息，計算兩個漢字的相鄰***現概率。互現信息體現了?
漢字之間結合關系的緊密程度。當緊密程度高於某壹個閾值時，便可認為此字組可能構成了壹個詞。這種方法?
只需對語料中的字組頻度進行統計，不需要切分詞典，因而又叫做無詞典分詞法或統計取詞方法。但這種方法?
也有壹定的局限性，會經常抽出壹些***現頻度高、但並不是詞的常用字組，例如“這壹”、“之壹”、“有的”、?
“我的”、“許多的”等，並且對常用詞的識別精度差，時空開銷大。實際應用的統計分詞系統都要使用壹部基本?
的分詞詞典（常用詞詞典）進行串匹配分詞，同時使用統計方法識別壹些新的詞，即將串頻統計和串匹配結合起來，?
既發揮匹配分詞切分速度快、效率高的特點，又利用了無詞典分詞結合上下文識別生詞、自動消除歧義的優點。?
另外壹類是基於統計機器學習的方法。首先給出大量已經分詞的文本，利用統計機器學習模型學習詞語切分的規律?
（稱為訓練），從而實現對未知文本的切分。我們知道，漢語中各個字單獨作詞語的能力是不同的，此外有的字常?
常作為前綴出現，有的字卻常常作為後綴（“者”“性”），結合兩個字相臨時是否成詞的信息，這樣就得到了許多?
與分詞有關的知識。這種方法就是充分利用漢語組詞的規律來分詞。這種方法的最大缺點是需要有大量預先分好詞?
的語料作支撐，而且訓練過程中時空開銷極大。?
到底哪種分詞算法的準確度更高，目前並無定論。對於任何壹個成熟的分詞系統來說，不可能單獨依靠某壹種算法?
來實現，都需要綜合不同的算法。例如，海量科技的分詞算法就采用“復方分詞法”，所謂復方，就是像中西醫結合?
般綜合運用機械方法和知識方法。對於成熟的中文分詞系統，需要多種算法綜合處理問題。?
"""?
#?Build?Inverted-Index?for?documents?
inverted?=?{}?
documents?=?{'doc1':doc1,?'doc2':doc2,?'doc3':doc3,?'doc4':doc4,?'doc5':doc5}?
for?doc_id,?text?in?documents.iteritems():?
doc_index?=?inverted_index(text)?
inverted_index_add(inverted,?doc_id,?doc_index)?
#?Search?one?word?
aWord?=?"分詞"?
result_a_word?=?search_a_word(inverted,?aWord)?
if?result_a_word:?
result_a_word_docs?=?result_a_word.keys()?
print?"'%s'?is?appeared?at"?%(aWord)?
for?result_a_word_doc?in?result_a_word_docs:?
result_a_word_index?=?result_a_word[result_a_word_doc]?
for?index?in?result_a_word_index:?
print?(str(index)?+?'?'),?
print?"of?"?+?result_a_word_doc?
print?""?
else:?
print?"No?matches!\r\n"?
#Search?more?than?one?word?
words?=?["漢語",?"切分"]?
result_words?=?search_words(inverted,?words)?
if?result_words:?
print?("["),?
for?i?in?range(len(words)):?
print?("%s?"?%(words[i])),?
print?("]?are?appeared?at?the?"),?
for?result_words_doc?in?result_words:?
print?(result_words_doc?+?'?'),?
print?"\r\n"?
else:?
print?"No?matches!\r\n"?
#Search?phrase?
phrase?=?"中文分詞"?
result_phrase?=?search_phrase(inverted,?phrase)?
if?result_phrase:?
result_phrase_docs?=?result_phrase.keys()?
print?"'%s'?is?appeared?at?the?"?%(phrase)?
for?result_phrase_doc?in?result_phrase_docs:?
result_phrase_index?=?result_phrase[result_phrase_doc]?
for?index?in?result_phrase_index:?
print?(str(index)?+?'?'),?
print?"of?"?+?result_phrase_doc?
print?""?
else:?
print?"No?matches!\r\n"