半隱式法python

『壹』 python是什麼

Python由荷蘭數學和計算機科學研究學會的Guido van Rossum 於1990
年代初設計，作為一門叫做ABC語言的替代品。Python提供了高效的高級數據結構，還能簡單有效地面向對象編程。Python語法和動態類型，以及解釋型語言的本質，使它成為多數平台上寫腳本和快速開發應用的編程語言，隨著版本的不斷更新和語言新功能的添加，逐漸被用於獨立的、大型項目的開發。
Python解釋器易於擴展，可以使用C或C++(或者其他可以通過C調用的語言)擴展新的功能和數據類型。Python
也可用於可定製化軟體中的擴展程序語言。Python豐富的標准庫，提供了適用於各個主要系統平台的源碼或機器碼。

『貳』 python 怎麼樣隱式函數調用

最常用的是在類定義的方法，給一個property的裝飾器，可以安裝調用屬性的方式調用

『叄』 python中指定參數問題

start,stop=0,start

與下面是等價的

temp=start
start=0
stop=temp

第一種寫法是python的一個特性，在後台做了與第二種寫法同樣的事，只是python把這些動作隱藏了，目的是讓代碼更簡潔

『肆』 如何利用Python做簡單的驗證碼識別

1摘要

驗證碼是目前互聯網上非常常見也是非常重要的一個事物，充當著很多系統的防火牆功能，但是隨時OCR技術的發展，驗證碼暴露出來的安全問題也越來越嚴峻。本文介紹了一套字元驗證碼識別的完整流程，對於驗證碼安全和OCR識別技術都有一定的借鑒意義。

然後經過了一年的時間，筆者又研究和get到了一種更強大的基於CNN卷積神經網路的直接端到端的驗證識別技術（文章不是我的，然後我把源碼整理了下，介紹和源碼在這裡面）：

基於python語言的tensorflow的『端到端』的字元型驗證碼識別源碼整理(github源碼分享)

2關鍵詞

關鍵詞：安全,字元圖片,驗證碼識別,OCR,Python,SVM,PIL

3免責聲明

本文研究所用素材來自於某舊Web框架的網站完全對外公開的公共圖片資源。

本文只做了該網站對外公開的公共圖片資源進行了爬取，並未越權做任何多餘操作。

本文在書寫相關報告的時候已經隱去漏洞網站的身份信息。

本文作者已經通知網站相關人員此系統漏洞，並積極向新系統轉移。

本報告的主要目的也僅是用於OCR交流學習和引起大家對驗證安全的警覺。

4引言

關於驗證碼的非技術部分的介紹，可以參考以前寫的一篇科普類的文章：

互聯網安全防火牆（1）--網路驗證碼的科普

裡面對驗證碼的種類，使用場景，作用，主要的識別技術等等進行了講解，然而並沒有涉及到任何技術內容。本章內容則作為它的技術補充來給出相應的識別的解決方案，讓讀者對驗證碼的功能及安全性問題有更深刻的認識。

5基本工具

要達到本文的目的，只需要簡單的編程知識即可，因為現在的機器學習領域的蓬勃發展，已經有很多封裝好的開源解決方案來進行機器學習。普通程序員已經不需要了解復雜的數學原理，即可以實現對這些工具的應用了。

主要開發環境：

• python3.5

• python SDK版本

• PIL

• 圖片處理庫

• libsvm

• 開源的svm機器學習庫

關於環境的安裝，不是本文的重點，故略去。

6基本流程

一般情況下，對於字元型驗證碼的識別流程如下：

• 准備原始圖片素材

• 圖片預處理

• 圖片字元切割

• 圖片尺寸歸一化

• 圖片字元標記

• 字元圖片特徵提取

• 生成特徵和標記對應的訓練數據集

• 訓練特徵標記數據生成識別模型

• 使用識別模型預測新的未知圖片集

• 達到根據「圖片」就能返回識別正確的字元集的目標

7素材准備

7.1素材選擇

由於本文是以初級的學習研究目的為主，要求「有代表性，但又不會太難」，所以就直接在網上找個比較有代表性的簡單的字元型驗證碼（感覺像在找漏洞一樣）。

最後在一個比較舊的網站（估計是幾十年前的網站框架）找到了這個驗證碼圖片。

原始圖：



• def get_feature(img): """


• 獲取指定圖片的特徵值,


• 1. 按照每排的像素點,高度為10,則有10個維度,然後為6列,總共16個維度


• :param img_path:


• :return:一個維度為10（高度）的列表 """



• width, height = img.size



• pixel_cnt_list = []


• height = 10 for y in range(height):


• pix_cnt_x = 0 for x in range(width): if img.getpixel((x, y)) == 0: # 黑色點


• pix_cnt_x += 1



• pixel_cnt_list.append(pix_cnt_x) for x in range(width):


• pix_cnt_y = 0 for y in range(height): if img.getpixel((x, y)) == 0: # 黑色點


• pix_cnt_y += 1



• pixel_cnt_list.append(pix_cnt_y) return pixel_cnt_list



然後就將圖片素材特徵化，按照libSVM指定的格式生成一組帶特徵值和標記值的向量文

『伍』 python構成一個程序最基本的三部分

python程序可以分解為模塊、語句、表達式和對象四部分
1，模塊包含語句
2，語句包含表達式
3，表達式建立並處理對象

『陸』 小白入門：用什麼寫Python

怎麼學python

俗話說得好，「摩天大樓從地起」，學習任何編程語言都一定要把該語言的基礎打牢，而怎麼打地基呢？秘訣只有一條：多敲代碼多敲代碼多敲代碼。學習前期建議找一本講python基礎的書或博客，把裡面的例題跟著操作一遍，在基礎打扎實後，可上一些比較出名的競賽項目的網站如kaggle等，通過做項目去鞏固知識。

推薦書籍:《Python基礎教程(第3版)》Magnus Lie Hetland著

推薦理由：全面介紹了Python的基礎知識、基本概念，高級主題，還有Python程序測試、打包、發布等知識，及10個具有實際意義的Python項目的開發過程，涉及的范圍較廣，既能為初學者夯實基礎，又能幫助程序員提升技能，適合各個層次的Python開發人員閱讀參考。

基礎知識

代碼規范

1. 縮進

相比於其他語言用大括弧和end來標識代碼塊，python語言比較「獨特」，其通過代碼的縮進來標識所屬代碼塊，通常4個空格為一個縮進，可用tab鍵實現。縮進是python代碼的重要組成部分，若你的代碼縮進格式不正確，如同一段代碼塊語句縮進不一致，首句未頂格等，都會運行出錯。

#一個完整的語句首句要頂格

i=0

#同一代碼塊的語句應縮進一致

for i in range(5):

print(i)

i+=1

2. 注釋

編程語言的注釋，即對代碼的解釋和說明。給代碼加上注釋，可提高代碼的可讀性，當你閱讀一段他人寫的代碼時，通過注釋迅速掌握代碼的大致意思，讀起代碼將更加得心應手。

python語言的注釋分為單行注釋和多行注釋，在注釋符後的內容計算機會自動跳過不去執行。

單行注釋：在需注釋語句前加「#」，可在代碼後使用，也可另起一行使用

i=1 #在代碼後使用注釋

#另起一行使用注釋

多行注釋：在語句開頭和結尾處加三個單引號或三個雙引號（前後須一致）

'''

使用單引號的多行注釋

'''

"""

使用雙引號的多行注釋

"""

使用注釋除了起到望文生義，迅速了解代碼意思的作用外，還有一個小妙處，可以將某段未完成或需要修改的代碼隱蔽起來，暫時不讓計算機執行。

2. 輸入語句

在python中獲取鍵盤輸入數據的函數是input()函數，input函數會自動將輸入的數據轉為字元串類型，並自動忽略換行符，同時可給出提示字元串。如果需要得到其他類型的數據，可對其進行強制性類型轉換。

input( )語法：

input([prompt])

input( )參數：

prompt: 給輸入者的提示信息，可選參數age=input("請輸入您的年齡：")

『柒』 隱式馬爾科夫模型 及 Python + HMMlearn的使用

hmmlearn

隱式馬爾科夫模型Hidden Markov Models(HMMs) 是一種通用的概率模型。一個可觀測的變數X的序列被一個內部的隱藏狀態Z所生成。其中，隱藏狀態Z無法被直接觀測。在隱藏狀態之間的轉移被假設是通過 馬爾科夫鏈(Markov chain) 的形式。
模型可以表示為 起始概率向量 和轉移概率矩陣 . 一個觀測量生成的概率可以是關於 的任意分布， 基於當前的隱藏狀態。

HMMs的3個基本問題:

hmmlearn 是Python支持HMMs的包。原來是sklearn的一部分，後來由於介面不一致分成單獨的包了。不過使用起來和sklearn的其他模型類似。

構造HMM model:

初始化的參數主要有 n_components , covariance_type , n_iter 。每個參數的作用我還沒有研究。

通過 fit 方法。
輸入是一個矩陣，包含拼接的觀察序列concatenated sequences of observation (也就是samples)，和序列的長度。

EM演算法是背後擬合模型的演算法。基於梯度優化的方法。通常會卡到一個局部極優值上。通常用戶需要用不同的初始化跑多次 fit ，然後選擇分數最高的模型。

分數通過 score 方法計算。
推導出的最優的隱藏狀態可以調用 predict 方法獲得。 predict 方法可以指定解碼器演算法。當前支持的有 viterbi （Vierbi algorithm）和 map (posteriori estimation)。

『捌』 如何解決python2不能隱式繼承

繼承是所有開發語言的必修內容，而本文寫的只是Python繼承中的特殊之處，關於繼承概念及內容可以自行網路（不裝B，感覺網路挺好的）1.構造函數：
要說繼承，先要說一下構造函數。Java要求是與類名相同並且無返回值，而Python則是強制要求命名為「__init__()」。
當創建類的對象時，會自動先調用構造函數，一般用於初始化。構造函數可以不寫，那麼程序會隱式自動增加一個空的構造函數。
2.繼承寫法：
(1).class 空格 類名稱 括弧內填寫父類名 冒號具體寫法如下class A:
def __init__(self):
pass
def print_class_name(self):
print "this is class A"
class B(A):
def __init__(self):
pass
if __name__ == "__main__":
class_b = B()
class_b.print_class_name()
上面代碼首先定義了一個名為「A」的類，包含一個名為「print_class_name」的方法。然後，定義一個名為「B」的類，繼承「A」，同時繼承了「A」類的「print_class_name」的方法。
此時「A」類為「B」類的父類或者叫基類，「B」類是「A」類的子類，子類會繼承父類的所有公共方法。
(2).意義：
一字記之曰「懶！」（感嘆號不算字）我始終相信賴人才能推動科學進步。
言歸正傳，假如你要寫一個老王類，包含年齡、性別等方法，後面還要寫一個老王的兒子小王類，也有年齡、性別等方法?
class FatherWang:
def __init__(self, age=43, sex='man'):
self.a = age
self.s = sex
def age(self):
print self.a
def sex(self):
print self.s
class SonWang:
def __init__(self, age=13, sex='man'):
self.a = age
self.s = sex
def age(self):
print self.a
def sex(self):
print self.s
if __name__ == "__main__":
father = FatherWang(43, "man")
father.age()
father.sex()
son = SonWang(13, "man")
son.age()
son.sex()
你會發現兩個類中有相同名稱和功能的方法，這樣寫豈不是很重復很累？(盡管按鍵盤次數不算太多，我依然覺得很累)如果有繼承就很好解決了。
class FatherWang:
def __init__(self, age=43, sex='man'):
self.a = age
self.s = sex
def age(self):
print self.a
def sex(self):
print self.s
class SonWang(FatherWang):
def __init__(self, age=13, sex='man'):
FatherWang.__init(age, sex)
if __name__ == "__main__":
father = FatherWang(43, "man")
father.age()
father.sex()
son = SonWang(13, "man")
son.age()
son.sex()
兩者運行結果完全一樣，但是使用繼承方法卻省了很多按鍵盤的次數。
3.經典類與新式類：
(1)經典類寫法：
class A:
pass
(2)新式類寫法：
class A(object):
pass
可以看出，新式類和經典類的區別在於，是否繼承object這個基類。object是所有類的父類。所以之前不帶「(object)」的寫法，屬於經典類寫法，加上「(object)」就是新式類的寫法。
(3).原因：這里我得吐槽一下Python的版本混亂。2.2版本之前只有經典類寫法，這里有一個問題，代碼如下?
class A:
pass
class B(object):
pass
a = A()
b = B()
print a.__class__
print type(a)
print "----------"
print b.__class__
print type(b)
結果為：
__main__.A
<type 'instance'>
----------
<class '__main__.B'>
<class '__main__.B'>
首先A類為經典類，B類為新式類。__class__屬性和type()方法都是返回對象類型，那麼問題來了，使用經典類的寫法返回結果卻不一致。因此在2.2版本之後出現了新式類來解決這個問題，自然，新式類和經典類還有更大的區別在後面說。另外在3.3版本中，無論使用哪種寫法，python都會隱式的繼承object，所以3.3版本不會再有經典類(在這里我只想問，早干什麼去了！)，但是鑒於3.3兼容性問題，貌似沒有太多人用。
4.方法重寫與方法重載
(1).方法重寫：
class FatherWang:
def __init__(self, age=43, sex='man'):
self.a = age
self.s = sex
def age(self):
print self.a
def sex(self):
print self.s
def name(self):
print "Wang_yang"
class SonWang(FatherWang):
def __init__(self, age=13, sex='man'):
FatherWang.__init(age, sex)
def name(self):
print "Wang_xiaoming"
if __name__ == "__main__":
father = FatherWang(43, "man")
father.age()
father.sex()
father.name()
son = SonWang(13, "man")
son.age()
son.sex()
son.name()
比繼承寫法(2)中的代碼相比，兩個類分別多了同名的方法「name」,之前說過子類會繼承父類的方法，那麼這時候兩個類有相同名字的方法，沖突了，怎麼處理？
這個時候，就叫方法重寫。可以理解為，子類的「name」方法把父類的「name」方法覆蓋了，重新寫了，所以調用子類的「name」方法時，會以子類的為准（盡管這種理解並不準確，但是可以很好解釋「方法重寫」這個名詞，後面會講到正確理解）。
注意下面的代碼
class FatherWang:
def __init__(self, age=43, sex="man"):
self.a = age
self.s = sex
print "I am FatherWang"
def age(self):
print "Father age:"+str(self.a)
def sex(self):
print "Father sex:"+str(self.s)
class MotherLi:
def __init__(self, age=40, sex="woman"):
self.a = age
self.s = sex
print "I am MotherLi"
def age(self):
print "Mother age:"+str(self.a)
def sex(self):
print "Mother sex"+str(self.s)
class SonWang(FatherWang, MotherLi):
def __init__(self, age=13, sex="man"):
FatherWang.__init__(self, age, sex)
MotherLi.__init__(self, age, sex)
print "I am SonWang"
if __name__ == "__main__":
son = SonWang()
son.age()
son.sex()
執行結果：
I am FatherWang
I am MotherLi
I am SonWang
Father age:13
Father sex:man
在之前代碼上稍作修改，另外增加了一個MotherLi的類，SonWang類繼承了FatherWang類和MotherLi類。注意，這是經典類的寫法。
首先，我們知道了python多繼承的寫法，就是在括弧中上一個父類後面加個逗號，然後再寫上下一個父類的名字：
class SonWang(FatherWang, MotherLi):
其次，FatherWang類和MotherLi類，都有名為age和sex方法，SonWang類為什麼會繼承FatherWang類的方法呢？那麼把SonWang類的繼承順序改一下class SonWang(MotherLi, FatherWang):
就會發現繼承的是MotherLi類的方法。
通過結果可知，是按照繼承的順序。
讓我們把代碼結構變得更發雜一些吧，我想會崩潰的，哈哈哈?
class Grandfather:
def __init__(self, age=73, sex="man"):
self.a = age
self.s = sex
print "I am Grandfather"
def age(self):
print "Grandfather age:"+str(self.a)
def sex(self):
print "Grandfather sex:"+str(self.s)
def Interesting(self):
print "Grandfather Interesting"
class Grandmother:
def __init__(self, age=70, sex="woman"):
self.a = age
self.s = sex
print "I am Grandmother"
def age(self):
print "Grandmother age:"+str(self.a)
def sex(self):
print "Grandmother sex:"+str(self.s)
def Interesting(self):
print "Grandmother Interesting"
class FatherWang(Grandfather, Grandmother):
def __init__(self, age=43, sex="man"):
self.a = age
self.s = sex
Grandfather.__init__(self, age, sex)
Grandmother.__init__(self, age, sex)
print "I am FatherWang"
def age(self):
print "Father age:"+str(self.a)
def sex(self):
print "Father sex:"+str(self.s)
class MotherLi(Grandfather, Grandmother):
def __init__(self, age=40, sex="woman"):
self.a = age
self.s = sex
Grandfather.__init__(self, age, sex)
Grandmother.__init__(self, age, sex)
print "I am MotherLi"
def age(self):
print "Mother age:"+str(self.a)
def sex(self):
print "Mother sex"+str(self.s)
def Interesting(self):
print "MotherLi Interesting"
class SonWang(FatherWang, MotherLi):
def __init__(self, age=13, sex="man"):
FatherWang.__init__(self, age, sex)
MotherLi.__init__(self, age, sex)
print "I am SonWang"
if __name__ == "__main__":
son = SonWang()
son.age()
son.sex()
son.Interesting()
執行結果：
I am Grandfather
I am Grandmother
I am FatherWang
I am Grandfather
I am Grandmother
I am MotherLi
I am SonWang
Father age:13
Father sex:man
Grandfather Interesting
話說，我自己都有點兒暈。簡單來講，就是兒子繼承了老爸、老媽，然後老爸繼承了爺爺、奶奶，媽媽繼承了老爺、姥姥。（真是一大家子啊）通過執行結果可知，兒子類先找到老爸類，然後再找老爸類的第1個父類爺爺類，此時發現爺爺類沒有父類了，那麼執行初始化。然後還要繼續找到老爸類的第2個父類奶奶類，此時發現奶奶類沒有父類了，執行初始化。此時老爸類的所有父類都初始化完成，初始化自己。然後開始找媽媽類……那麼為什麼Interesting方法會使用爺爺類的呢？奶奶類、老爺類、姥姥類都有啊？首先兒子類沒有Interesting方法，會先找第1個父類老爸類。發現老爸類也沒有，再找老爸類的第1個父類，發現找到了，那麼就直接調用不再往下找了。
結論：經典類的多繼承，按照繼承順序查找。即，從左到右，從下到上的方式。注意，只有經典類是這樣的！
(2).新式類的多繼承：
class Grandfather(object):
def __init__(self, age=73, sex="man"):
self.a = age
self.s = sex
print "I am Grandfather"
def age(self):
print "Grandfather age:"+str(self.a)
def sex(self):
print "Grandfather sex:"+str(self.s)
def Interesting(self):
print "Grandfather Interesting"
class Grandmother(object):
def __init__(self, age=70, sex="woman"):
self.a = age
self.s = sex
print "I am Grandmother"
def age(self):
print "Grandmother age:"+str(self.a)
def sex(self):
print "Grandmother sex:"+str(self.s)
def Interesting(self):
print "Grandmother Interesting"
class FatherWang(Grandfather, Grandmother):
def __init__(self, age=43, sex="man"):
self.a = age
self.s = sex
Grandfather.__init__(self, age, sex)
Grandmother.__init__(self, age, sex)
print "I am FatherWang"
def age(self):
print "Father age:"+str(self.a)
def sex(self):
print "Father sex:"+str(self.s)
class MotherLi(Grandfather, Grandmother):
def __init__(self, age=40, sex="woman"):
self.a = age
self.s = sex
Grandfather.__init__(self, age, sex)
Grandmother.__init__(self, age, sex)
print "I am MotherLi"
def age(self):
print "Mother age:"+str(self.a)
def sex(self):
print "Mother sex"+str(self.s)
def Interesting(self):
print "MotherLi Interesting"
class SonWang(FatherWang, MotherLi):
def __init__(self, age=13, sex="man"):
FatherWang.__init__(self, age, sex)
MotherLi.__init__(self, age, sex)
print "I am SonWang"
if __name__ == "__main__":
son = SonWang()
son.age()
son.sex()
son.Interesting()
執行結果：
I am Grandfather
I am Grandmother
I am FatherWang
I am Grandfather
I am Grandmother
I am MotherLi
I am SonWang
Father age:13
Father sex:man
MotherLi Interesting

『玖』 Python中文分詞的原理你知道嗎

中文分詞，即 Chinese Word Segmentation，即將一個漢字序列進行切分，得到一個個單獨的詞。表面上看，分詞其實就是那麼回事，但分詞效果好不好對信息檢索、實驗結果還是有很大影響的，同時分詞的背後其實是涉及各種各樣的演算法的。

中文分詞與英文分詞有很大的不同，對英文而言，一個單詞就是一個詞，而漢語是以字為基本的書寫單位，詞語之間沒有明顯的區分標記，需要人為切分。根據其特點，可以把分詞演算法分為四大類：

基於規則的分詞方法

基於統計的分詞方法

基於語義的分詞方法

基於理解的分詞方法

下面我們對這幾種方法分別進行總結。

基於規則的分詞方法

這種方法又叫作機械分詞方法、基於字典的分詞方法，它是按照一定的策略將待分析的漢字串與一個「充分大的」機器詞典中的詞條進行匹配。若在詞典中找到某個字元串，則匹配成功。該方法有三個要素，即分詞詞典、文本掃描順序和匹配原則。文本的掃描順序有正向掃描、逆向掃描和雙向掃描。匹配原則主要有最大匹配、最小匹配、逐詞匹配和最佳匹配。

最大匹配法（MM）。基本思想是：假設自動分詞詞典中的最長詞條所含漢字的個數為 i，則取被處理材料當前字元串序列中的前 i 個字元作為匹配欄位，查找分詞詞典，若詞典中有這樣一個 i 字詞，則匹配成功，匹配欄位作為一個詞被切分出來；若詞典中找不到這樣的一個 i 字詞，則匹配失敗，匹配欄位去掉最後一個漢字，剩下的字元作為新的匹配欄位，再進行匹配，如此進行下去，直到匹配成功為止。統計結果表明，該方法的錯誤率 為 1/169。

逆向最大匹配法（RMM）。該方法的分詞過程與 MM 法相同，不同的是從句子（或文章）末尾開始處理，每次匹配不成功時去掉的是前面的一個漢字。統計結果表明，該方法的錯誤率為 1/245。

逐詞遍歷法。把詞典中的詞按照由長到短遞減的順序逐字搜索整個待處理的材料，一直到把全部的詞切分出來為止。不論分詞詞典多大，被處理的材料多麼小，都得把這個分詞詞典匹配一遍。

設立切分標志法。切分標志有自然和非自然之分。自然切分標志是指文章中出現的非文字元號，如標點符號等；非自然標志是利用詞綴和不構成詞的詞（包 括單音詞、復音節詞以及象聲詞等）。設立切分標志法首先收集眾多的切分標志，分詞時先找出切分標志，把句子切分為一些較短的欄位，再用 MM、RMM 或其它的方法進行細加工。這種方法並非真正意義上的分詞方法，只是自動分詞的一種前處理方式而已，它要額外消耗時間掃描切分標志，增加存儲空間存放那些非 自然切分標志。

最佳匹配法（OM）。此法分為正向的最佳匹配法和逆向的最佳匹配法，其出發點是：在詞典中按詞頻的大小順序排列詞條，以求縮短對分詞詞典的檢索時 間，達到最佳效果，從而降低分詞的時間復雜度，加快分詞速度。實質上，這種方法也不是一種純粹意義上的分詞方法，它只是一種對分詞詞典的組織方式。OM 法的分詞詞典每條詞的前面必須有指明長度的數據項，所以其空間復雜度有所增加，對提高分詞精度沒有影響，分詞處理的時間復雜度有所降低。

此種方法優點是簡單，易於實現。但缺點有很多：匹配速度慢；存在交集型和組合型歧義切分問題；詞本身沒有一個標準的定義，沒有統一標準的詞集；不同詞典產生的歧義也不同；缺乏自學習的智能性。

基於統計的分詞方法

該方法的主要思想：詞是穩定的組合，因此在上下文中，相鄰的字同時出現的次數越多，就越有可能構成一個詞。因此字與字相鄰出現的概率或頻率能較好地反映成詞的可信度。可以對訓練文本中相鄰出現的各個字的組合的頻度進行統計，計算它們之間的互現信息。互現信息體現了漢字之間結合關系的緊密程度。當緊密程 度高於某一個閾值時，便可以認為此字組可能構成了一個詞。該方法又稱為無字典分詞。

該方法所應用的主要的統計模型有：N 元文法模型（N-gram）、隱馬爾可夫模型（Hiden Markov Model，HMM）、最大熵模型（ME）、條件隨機場模型（Conditional Random Fields，CRF）等。

在實際應用中此類分詞演算法一般是將其與基於詞典的分詞方法結合起來，既發揮匹配分詞切分速度快、效率高的特點，又利用了無詞典分詞結合上下文識別生詞、自動消除歧義的優點。

基於語義的分詞方法

語義分詞法引入了語義分析，對自然語言自身的語言信息進行更多的處理，如擴充轉移網路法、知識分詞語義分析法、鄰接約束法、綜合匹配法、後綴分詞法、特徵詞庫法、矩陣約束法、語法分析法等。

擴充轉移網路法

該方法以有限狀態機概念為基礎。有限狀態機只能識別正則語言，對有限狀態機作的第一次擴充使其具有遞歸能力，形成遞歸轉移網路 （RTN）。在RTN 中，弧線上的標志不僅可以是終極符（語言中的單詞）或非終極符（詞類），還可以調用另外的子網路名字分非終極符（如字或字串的成詞條件）。這樣，計算機在 運行某個子網路時，就可以調用另外的子網路，還可以遞歸調用。詞法擴充轉移網路的使用， 使分詞處理和語言理解的句法處理階段交互成為可能，並且有效地解決了漢語分詞的歧義。

矩陣約束法

其基本思想是：先建立一個語法約束矩陣和一個語義約束矩陣， 其中元素分別表明具有某詞性的詞和具有另一詞性的詞相鄰是否符合語法規則， 屬於某語義類的詞和屬於另一詞義類的詞相鄰是否符合邏輯，機器在切分時以之約束分詞結果。

基於理解的分詞方法

基於理解的分詞方法是通過讓計算機模擬人對句子的理解，達到識別詞的效果。其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現象。它通常包括三個部分：分詞子系統、句法語義子系統、總控部分。在總控部分的協調下，分詞子系統可以獲得有關詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。目前基於理解的分詞方法主要有專家系統分詞法和神經網路分詞法等。

專家系統分詞法

從專家系統角度把分詞的知識（包括常識性分詞知識與消除歧義切分的啟發性知識即歧義切分規則）從實現分詞過程的推理機中獨立出來，使知識庫的維護與推理機的實現互不幹擾，從而使知識庫易於維護和管理。它還具有發現交集歧義欄位和多義組合歧義欄位的能力和一定的自學習功能。

神經網路分詞法

該方法是模擬人腦並行，分布處理和建立數值計算模型工作的。它將分詞知識所分散隱式的方法存入神經網路內部，通過自學習和訓練修改內部權值，以達到正確的分詞結果，最後給出神經網路自動分詞結果，如使用 LSTM、GRU 等神經網路模型等。

神經網路專家系統集成式分詞法

該方法首先啟動神經網路進行分詞，當神經網路對新出現的詞不能給出准確切分時，激活專家系統進行分析判斷，依據知識庫進行推理，得出初步分析，並啟動學習機制對神經網路進行訓練。該方法可以較充分發揮神經網路與專家系統二者優勢，進一步提高分詞效率。

以上便是對分詞演算法的基本介紹。

『拾』 如何用Python編寫一個素數環

此文主要目的，是向大家展示如何才能用python語言，來部署STARK演算法。
STARKs（可擴容的透明知識論證）是創建一種證明的技術，這項證明中f(x)=y，其中f可能要花很長的時間來進行計算，但是這個證明可以被很快驗證。STARK是「雙重擴容」：對於一個需要t步驟的計算，這會花費大約O(t * log(t))步驟才能完成這個證明，這可能是最優的情況，而且這需要通過~O(log2(t))個步驟才能驗證，對於中等大小的T值，它比原始計算快得多。STARKs也擁有隱私保護的「零知識證明」的特性，雖然我們將這類使用案例應用到其中，從而完成可驗證的延遲功能，不需要這類性質，所以我們不用擔心。
首先，先請幾項說明：
這個代碼還沒有完全審核；在實際使用案例中的情況，還不能保證
這部分代碼是還沒有達到理想狀態（是用Python語言寫的）
STARKs 的「真實情況」 傾向於使用二進制欄位而不是素數域的特定應用程序效率的原因；但是，他們確實也表現出，這里寫出的代碼是合法並且可用的。
沒有一個真實的方法來使用STARK。它是一個非常寬泛的加密和數學架構，同時為不同的應用有不同的設置，以及連續的研究來減少證明者和驗證者的復雜性，同時提高可用性。
此文希望大家能夠知道，模運算和素數域是如何運行的，
並且和多項式概念，插值和估值進行結合。
現在，讓我們一起來了解吧！
MIMC
下面是STARK的功能展示：
def mimc(inp, steps, round_constants): start_time = time.time() for i in range(steps-1): inp = (inp**3 + round_constants[i % len(round_constants)]) % molus print("MIMC computed in %.4f sec" % (time.time() - start_time)) return inp
我們選擇MIMC作為案例，因為它（i）很容易理解，（ii）在真實世界使用的很多。函數功能見下圖：
注意：在很多關於MIMC的討論中，你可以典型地看出使用了XOR，而不是+；這是因為MIMC可以在二進制情況下使用，其中添加是XOR；這里我們會在素數領域進行。
在我們的案例中，常數相對而言會是比較小的列表（例如，64位），這會一直連續地進行周期循環（也就說，在k[64]之後）。MIMC自身可以獲得這個特性，因為MIMC可以向後進行計算（從相應的輸出獲得輸入），但是往後計算需要比向前計算多花費100倍的時間（並且沒有方向可以同步進行）。所以你可以將往後計算的功能想像成計算不能同步的工作量證明，並且往前方向計算的功能可以作為驗證的過程。
x -> x(2p-1)/3 是x -> x3 的反函數；根據費馬小定理，這是真實的，盡管這個定理沒有費馬大定理出名，但是依然對數學的貢獻很大。
我們嘗試使用STARK來進行更加有效的驗證，而不是讓驗證者必須在向前方向運行MIMC，在完成向後計算之後，證明者可以在向前方向進行STARK計算，並且驗證者可以很簡單地驗證STARK。我們希望計算STARK可以比MIMC向前和向後之間的運行速度差別要小，所以證明者的時間仍然是有初始的向後計算來主導的。而並不是STARK計算。STARK的認證會相對較快（在python語言演算法中，可以是0.05-0.3秒），不論初始的計算時間有多長。
所有的計算會在2256 – 351 * 232 + 1個模內完成；我們使用素數模，因為它是小於2256 最大的素數，其中乘法群包含了232 個子集（也就是說，有這樣一個數g，從而在完全232次循環之後，G素數環的連續冪模繞回到1），而且是按照6k+5的形式。首個特性是保證FFT和FRI演算法的有效版本，其次是保證MIMC實際上可以向後計算（請見上面提到的x -> x(2p-1)/3 使用方法）。
素域操作
我們通過建立方便的等級來進行素域的操作，同時也有多項式的操作。代碼如下，收首先是小數位數：
class PrimeField(): def __init__(self, molus): # Quick primality test assert pow(2, molus, molus) == 2 self.molus = molus def add(self, x, y): return (x+y) % self.molus def sub(self, x, y): return (x-y) % self.molus def mul(self, x, y): return (x*y) % self.molus
並且使用擴展歐幾里得演算法，來計算模塊逆轉（這和在素域中計算1/x相同）：
# Molar inverse using the extended Euclidean algorithm def inv(self, a): if a == 0: return 0 lm, hm = 1, 0 low, high = a % self.molus, self.molus while low > 1: r = high//low nm, new = hm-lm*r, high-low*r lm, low, hm, high = nm, new, lm, low return lm % self.molus
上面的演算法是相對昂貴的；幸運地是，對於特定的案例，我們需要做很多的模逆計算，有一個數學方法可以讓我們來計算很多逆運算，被稱為蒙哥馬利批量求逆：
使用蒙哥馬利批量求逆來計算模逆，其輸入為紫色，輸出為綠色，乘法門為黑色，紅色方塊是唯一的模逆。
下面的代碼是演算法的體現，其中包含一些特別的邏輯。如果我們正在求逆的集合中包含零，那麼它會將這些零的逆設置為 0 並繼續前進。
def multi_inv(self, values): partials = [1] for i in range(len(values)): partials.append(self.mul(partials[-1], values[i] or 1)) inv = self.inv(partials[-1]) outputs = [0] * len(values) for i in range(len(values), 0, -1): outputs[i-1] = self.mul(partials[i-1], inv) if values[i-1] else 0 inv = self.mul(inv, values[i-1] or 1) return outputs
這部分演算法接下來會驗證稱為非常重要的東西，特別是當我們開始和不同階的多項式進行計算的時候。
現在我們來看看一些多項式計算。我們把多項式當做一個數據集，其中的i是第i階（例如，x3 + 2x + 1變成[1, 2, 0, 1]）。下面就是在一個點進行多項式估算的方法：
# Evaluate a polynomial at a point def eval_poly_at(self, p, x): y = 0 power_of_x = 1 for i, p_coeff in enumerate(p): y += power_of_x * p_coeff power_of_x = (power_of_x * x) % self.molus return y % self.molus
困難和挑戰
f.eval_poly_at([4, 5, 6], 2)的輸出是多少？模是31嗎？
下面的解釋就是答案
.其實也有代碼是多項式加法，減法，乘法和除法；這是很長的加減乘除運算。有一個很重要的內容是拉格朗日插值，它將一組 x 和 y 坐標作為輸入，並返回通過所有這些點的最小多項式（你可以將其視為多項式求值的逆）：
# Build a polynomial that returns 0 at all specified xs def zpoly(self, xs): root = [1] for x in xs: root.insert(0, 0) for j in range(len(root)-1): root[j] -= root[j+1] * x return [x % self.molus for x in root] def lagrange_interp(self, xs, ys): # Generate master numerator polynomial, eg. (x - x1) * (x - x2) * ... * (x - xn) root = self.zpoly(xs) # Generate per-value numerator polynomials, eg. for x=x2, # (x - x1) * (x - x3) * ... * (x - xn), by dividing the master # polynomial back by each x coordinate nums = [self.div_polys(root, [-x, 1]) for x in xs] # Generate denominators by evaluating numerator polys at each x denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))] invdenoms = self.multi_inv(denoms) # Generate output polynomial, which is the sum of the per-value numerator # polynomials rescaled to have the right y values b = [0 for y in ys] for i in range(len(xs)): yslice = self.mul(ys[i], invdenoms[i]) for j in range(len(ys)): if nums[i][j] and ys[i]: b[j] += nums[i][j] * yslice return [x % self.molus for x in b]
相關數學知識請參見此文的M-N部分。需要注意，我們也會有特別的方法lagrange_interp_4和lagrange_interp_2來加速次數小於 2 的拉格朗日插值和次數小於 4 的多項式運算。
快速傅立葉變換
如果你仔細閱讀上面的演算法，你也許會發現拉格朗日插值和多點求值（即求在N個點處次數小於N的多項式的值）都需要耗費2次時間，例如對於1000個點求拉格朗日插值，需要幾百萬個步驟，而且100萬個點的拉格朗日插值需要萬億個步驟。這是不可接受的低效率，所以我們需要使用更加有效的演算法，快速傅立葉變換。
FFT只需要花費O(n * log(n))的時間（也就是說，1000個點的計算需要10,000步，100萬個點的計算需要2000步），雖然它的范圍更受限制；x坐標必須是單位根部的完全集合，必須滿足N = 2k 階。也就是說，如果有N個點，那麼x坐標必須某個P值的連續冪，1, p, p2, p3…，其中pN = 1。這個演算法能夠用來進行多點計算和插值計算，而且只需要調整一個小參數。
下面就是演算法詳情（這是個簡單的表達方式；更詳細內容可以參閱此處代碼）
def fft(vals, molus, root_of_unity): if len(vals) == 1: return vals L = fft(vals[::2], molus, pow(root_of_unity, 2, molus)) R = fft(vals[1::2], molus, pow(root_of_unity, 2, molus)) o = [0 for i in vals] for i, (x, y) in enumerate(zip(L, R)): y_times_root = y*pow(root_of_unity, i, molus) o[i] = (x+y_times_root) % molus o[i+len(L)] = (x-y_times_root) % molus return o def inv_fft(vals, molus, root_of_unity): f = PrimeField(molus) # Inverse FFT invlen = f.inv(len(vals)) return [(x*invlen) % molus for x in fft(vals, molus, f.inv(root_of_unity))]
你可以自己通過一些輸入來運行代碼，並且看看是否能得到想要的結果，當你使用eval_poly_at的時候，給出你期望得到的答案。例如：
>>> fft.fft([3,1,4,1,5,9,2,6], 337, 85, inv=True) [46, 169, 29, 149, 126, 262, 140, 93] >>> f = poly_utils.PrimeField(337) >>> [f.eval_poly_at([46, 169, 29, 149, 126, 262, 140, 93], f.exp(85, i)) for i in range(8)] [3, 1, 4, 1, 5, 9, 2, 6]
傅里葉變換會把[x[0] …. x[n-1]]作為輸入，並且它的目標是輸出x[0] + x[1] + … + x[n-1]作為首個元素，x[0] + x[1] * 2 + … + x[n-1] * w**(n-1)作為第二個元素，等等；快速傅里葉變換可以通過把數據分為兩半，來完成這個，在兩邊都進行FFT，然後將結果結合在一起。
上圖就是信息如何進行FFT運算的解釋。請注意FFT是如何進行兩次數據復制，並且進行粘合，直到你得到一個元素。
現在，我們把所有部分組合起來，看看整件事情是如何：def mk_mimc_proof(inp, steps, round_constants)，它生成運行 MIMC 函數的執行結果的證明，其中給定的輸入為步驟數。首先，是一些 assert 函數：
# Calculate the set of x coordinates xs = get_power_cycle(root_of_unity, molus) column = [] for i in range(len(xs)//4): x_poly = f.lagrange_interp_4( [xs[i+len(xs)*j//4] for j in range(4)], [values[i+len(values)*j//4] for j in range(4)], ) column.append(f.eval_poly_at(x_poly, special_x))
擴展因子是我們將要拉伸的計算軌跡（執行 MIMC 函數的「中間值」的集合）。
m2 = merkelize(column) # Pseudo-randomly select y indices to sample # (m2[1] is the Merkle root of the column) ys = get_pseudorandom_indices(m2[1], len(column), 40) # Compute the Merkle branches for the values in the polynomial and the column branches = [] for y in ys: branches.append([mk_branch(m2, y)] + [mk_branch(m, y + (len(xs) // 4) * j) for j in range(4)])
我們需要步數乘以擴展因子最多為 2^32，因為當 k > 32 時，我們沒有 2^k 次的單位根。
computational_trace_polynomial = inv_fft(computational_trace, molus, subroot) p_evaluations = fft(computational_trace_polynomial, molus, root_of_unity)
我們首個計算會是得出計算軌跡；也就是說，所有的計算中間值，從輸入到輸出。
assert steps <= 2**32 // extension_factor assert is_a_power_of_2(steps) and is_a_power_of_2(len(round_constants)) assert len(round_constants) < steps
然後，我們會從將計算軌跡轉換為多項式，在單位根 g （其中，g^steps = 1）的連續冪的軌跡上「放下」連續值，然後我們對更大的集合——即單位根 g2 的連續冪，其中 g2^steps * 8 = 1（注意 g2^8 = g）的多項式求值。
# Generate the computational trace computational_trace = [inp] for i in range(steps-1): computational_trace.append((computational_trace[-1]**3 + round_constants[i % len(round_constants)]) % molus) output = computational_trace[-1]
黑色： g1 的冪。紫色： g2 的冪。橙色：1。你可以將連續的單位根看作一個按這種方式排列的圓圈。我們沿著 g1的冪「放置」計算軌跡，然後擴展它來計算在中間值處（即 g2 的冪）的相同多項式的值。
我們可以將MIMC的循環常數轉換為多項式。因為這些循環常數鏈是非常通常發生地（在我們的測試中，每64個步驟都會進行），最終證明他們形成了64階的多項式，而且外面可以很容易計算出它的表達式，以及擴展式：
skips2 = steps // len(round_constants) constants_mini_polynomial = fft(round_constants, molus, f.exp(subroot, skips2), inv=True) constants_polynomial = [0 if i % skips2 else constants_mini_polynomial[i//skips2] for i in range(steps)] constants_mini_extension = fft(constants_mini_polynomial, molus, f.exp(root_of_unity, skips2))
假設其中有8192個步驟，並且有64個循環常數。這是我們想要做的：我們正在進行FFT，從而計算循環常數來作為g1128 的功能。然後我們在之間加入很多零，來完成g1本身的功能。因為g1128 大約每64步進行循環，我們知道g1這個功能也會同樣。我們只計算這個擴展中的512個步驟，因為我們知道這個擴展會在每512步之後重復。現在，我們按照斐波那契案例中那樣，計算C(P(x))，除了這次是計算，需要注意，我們不在計算使用系數形式的多項式；而是根據高次單位根的連續冪來對多項式進行求值。
c_of_p需要滿足Q(x) = C(P(x), P(g1*x)，K(x)) = P(g1*x) – P(x)**3 – K(x)；目標是對於任何我們放入計算軌道的x（除了最後一步，因為在最後一步之後，就沒有步驟），計算軌跡中的下個數值就和之前的相等，再加上循環常量。與第1部分中的斐波那契示例不同，其中如果某個計算步驟是在k向量，下個就會是k+1向量，我們把低次單位根（ g1 ）的連續冪放下計算軌跡，所以如果某個計算步驟是在x = g1i ，下個步驟就會在g1i+1 = g1i * g1 = x * g1。因此，對於低階單位根（ g1 ）的每一個冪，我們希望最終會是P(x*g1) = P(x)**3 + K(x)，或者P(x*g1) – P(x)**3 – K(x) = Q(x) = 0。因此，Q(x) 會在低次單位根 g 的所有連續冪上等於零（除了最後一個）。
# Create the composed polynomial such that # C(P(x), P(g1*x), K(x)) = P(g1*x) - P(x)**3 - K(x) c_of_p_evaluations = [(p_evaluations[(i+extension_factor)%precision] - f.exp(p_evaluations[i], 3) - constants_mini_extension[i % len(constants_mini_extension)]) % molus for i in range(precision)] print('Computed C(P, K) polynomial')
有個代數定理證明，如果Q(x)在所有這些x坐標，都等於零，那麼最小多項式的乘積就會在所有這些x坐標等於零：Z(x) = (x – x_1) * (x – x_2) * … * (x – x_n)。通過證明在任何單個的坐標，Q(x)是等於零，我們想要證明這個很難，因為驗證這樣的證明比運行原始計算需要耗費更長的時間，我們會使用一個間接的方式來證明Q(x)是Z(x)的乘積。並且我們會怎麼做呢？通過證明D(x) = Q(x) / Z(x)，並且使用FRI來證明它其實是個多項式，而不是個分數。
我們選擇低次單位根和高次單位根的特定排列，因為事實證明，計算Z(x)，而且除以Z(x)也十分簡單：Z 的表達式是兩項的一部分。
需要注意地是，直接計算Z的分子和分母，然後使用批量模逆的方法將除以Z轉換為乘法，隨後通過 Z(X) 的逆來逐點乘以 Q(x) 的值。需要注意，對於低次單位根的冪，除了最後一個，都可以得到Z(x) = 0，所以這個計算包含其逆計算就會中斷。這是非常不幸的，雖然我們會通過簡單地修改隨機檢查和FRI演算法來堵住這個漏洞，所以就算我們計算錯誤，也沒關系。
因為Z(x)可以簡潔地表達，我們也可以獲得另個好處：驗證者對於任何特別的x，可以快速計算Z(x)，而且還不需要任何提前計算。對於證明者來說，我們可以接受證明者必須處理大小等於步數的多項式，但我們不想讓驗證者做同樣的事情，因為我們希望驗證過程足夠簡潔。
# Compute D(x) = Q(x) / Z(x) # Z(x) = (x^steps - 1) / (x - x_atlast_step) z_num_evaluations = [xs[(i * steps) % precision] - 1 for i in range(precision)] z_num_inv = f.multi_inv(z_num_evaluations) z_den_evaluations = [xs[i] - last_step_position for i in range(precision)] d_evaluations = [cp * zd * zni % molus for cp, zd, zni in zip(c_of_p_evaluations, z_den_evaluations, z_num_inv)] print('Computed D polynomial')
在幾個隨機點上，進行概念檢測D(x) * Z(x) = Q(x)，從而可以驗證轉賬約束，每個計算步驟是之前步驟的有效結果。但是我們也想驗證邊界約束，其中計算的輸入和輸出就是證明者所說的那樣。只是要求證明者提供P(1), D(1), P(last_step)還有D(last_step)的數值，這些都是很脆弱的；沒有證明，那些數值都是在同個多項式。所以，我們使用類似的多項式除法技巧：
# Compute interpolant of ((1, input), (x_atlast_step, output)) interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output]) i_evaluations = [f.eval_poly_at(interpolant, x) for x in xs] zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1]) inv_z2_evaluations = f.multi_inv([f.eval_poly_at(quotient, x) for x in xs]) # B = (P - I) / Z2 b_evaluations = [((p - i) * invq) % molus for p, i, invq in zip(p_evaluations, i_evaluations, inv_z2_evaluations)] print('Computed B polynomial')
那麼，我們的論證如下。證明者想要證明P(1) == input和P(last_step) == output。如果我們將I(x)作為插值，那麼就是穿越(1, input)和(last_step, output)亮點的線，於是P(x) – I(x)就會在這亮點上等於零。因此，它會證明P(x) – I(x)是P(x) – I(x)的乘積，並且我們通過提高商數來證明這點。
紫色：計算軌跡多項式 (P) 。綠色：插值 (I)（注意插值是如何構造的，其在 x = 1 處等於輸入（應該是計算軌跡的第一步），在 x=g^(steps-1) 處等於輸出（應該是計算軌跡的最後一步）。紅色：P-I。黃色：在x = 1和 x=g^(steps-1)（即 Z2）處等於 0 的最小多項式。粉紅色：(P – I) / Z2。
現在，我們來看看將P，D和B的默克爾根部組合在一起。
現在，我們需要證明P，D和B其實都是多項式，並且是最大的正確階數。但是FRI證明是很大且昂貴的，而且我們不想有三個FRI證明，所以，我們計算 P，D 和 B 的偽隨機線性組合，並且基於它來進行FRI證明：
# Compute their Merkle roots mtree = merkelize([pval.to_bytes(32, 'big') + dval.to_bytes(32, 'big') + bval.to_bytes(32, 'big') for pval, dval, bval in zip(p_evaluations, d_evaluations, b_evaluations)]) print('Computed hash root')
除非所有這三個多項式有正確的低階，不然幾乎不可能有隨機選擇的線性組合，所以這很足夠。
我們想要證明D的階數小於2 * steps，而且P 和 B 的次數小於steps，所以我們其實使用了隨機的P, P * xsteps, B, Bsteps 和 D的隨機組合，並且可以看出這部分組合是小於2 * steps。
現在，我們來檢查下所有的多項式組合。我們先獲得很多隨機的索引，然後在這些索引上為默克爾樹枝提供多項式：
k1 = int.from_bytes(blake(mtree[1] + b'\x01'), 'big') k2 = int.from_bytes(blake(mtree[1] + b'\x02'), 'big') k3 = int.from_bytes(blake(mtree[1] + b'\x03'), 'big') k4 = int.from_bytes(blake(mtree[1] + b'\x04'), 'big') # Compute the linear combination. We don't even bother calculating it # in coefficient form; we just compute the evaluations root_of_unity_to_the_steps = f.exp(root_of_unity, steps) powers = [1] for i in range(1, precision): powers.append(powers[-1] * root_of_unity_to_the_steps % molus) l_evaluations = [(d_evaluations[i] + p_evaluations[i] * k1 + p_evaluations[i] * k2 * powers[i] + b_evaluations[i] * k3 + b_evaluations[i] * powers[i] * k4) % molus for i in range(precision)]
get_pseudorandom_indices函數會回復[0…precision-1]范圍中的隨機索引，而且exclude_multiples_of參數並不會給出特定參數倍數的值。這就保證了，我們不會沿著原始計算軌跡進行采樣，否則就會獲得錯誤的答案。
證明是由一組默克爾根、經過抽查的分支以及隨機線性組合的低次證明組成：
# Do some spot checks of the Merkle tree at pseudo-random coordinates, excluding # multiples of `extension_factor` branches = [] samples = spot_check_security_factor positions = get_pseudorandom_indices(l_mtree[1], precision, samples, exclude_multiples_of=extension_factor) for pos in positions: branches.append(mk_branch(mtree, pos)) branches.append(mk_branch(mtree, (pos + skips) % precision)) branches.append(mk_branch(l_mtree, pos)) print('Computed %d spot checks' % samples)
整個證明最長的部分是默克爾樹分支，還有FRI證明，這是有更多分支來組成的。這是驗證者的實質結果：
o = [mtree[1], l_mtree[1], branches, prove_low_degree(l_evaluations, root_of_unity, steps * 2, molus, exclude_multiples_of=extension_factor)]
在每個位置，證明者需要提供一個默克爾證明，從而讓驗證者能夠檢查這個默克爾證明，並且檢查C(P(x), P(g1*x), K(x)) = Z(x) * D(x)以及B(x) * Z2(x) + I(x) = P(x)（提醒：對於不在初始計算軌道上的x，Z(x)不會是零，所以C(P(x), P(g1*x), K(x)也不會是零)。驗證者也會檢查線性組合是正確的，然後調用。
for i, pos in enumerate(positions): x = f.exp(G2, pos) x_to_the_steps = f.exp(x, steps) mbranch1 = verify_branch(m_root, pos, branches[i*3]) mbranch2 = verify_branch(m_root, (pos+skips)%precision, branches[i*3+1]) l_of_x = verify_branch(l_root, pos, branches[i*3 + 2], output_as_int=True) p_of_x = int.from_bytes(mbranch1[:32], 'big') p_of_g1x = int.from_bytes(mbranch2[:32], 'big') d_of_x = int.from_bytes(mbranch1[32:64], 'big') b_of_x = int.from_bytes(mbranch1[64:], 'big') zvalue = f.div(f.exp(x, steps) - 1, x - last_step_position) k_of_x = f.eval_poly_at(constants_mini_polynomial, f.exp(x, skips2)) # Check transition constraints Q(x) = Z(x) * D(x) assert (p_of_g1x - p_of_x ** 3 - k_of_x - zvalue * d_of_x) % molus == 0 # Check boundary constraints B(x) * Z2(x) + I(x) = P(x) interpolant = f.lagrange_interp_2([1, last_step_position], [inp, output]) zeropoly2 = f.mul_polys([-1, 1], [-last_step_position, 1]) assert (p_of_x - b_of_x * f.eval_poly_at(zeropoly2, x) - f.eval_poly_at(interpolant, x)) % molus == 0 # Check correctness of the linear combination assert (l_of_x - d_of_x - k1 * p_of_x - k2 * p_of_x * x_to_the_steps - k3 * b_of_x - k4 * b_of_x * x_to_the_steps) % molus == 0
其實還沒有完成成功；證明對跨多項式檢查和 FRI 所需的抽查次數的可靠性分析是非常棘手的。但是這些就是所有代碼，至少你不用擔心進行瘋狂的優化。當我運行以上代碼的時候，我們會獲得STARK證明，會有300-400倍的證明成本例如，一個需要 0.2 秒的 MIMC 計算需要 60 秒來證明）。這就使得4核機器計算MIMC中的 STARK，實際上可以比後向計算 MIMC 更快。也就是說，在python語言，這會相對低效的實現，並且這也會證明運行時間比例會不同。同時，也值得指出，MIMC 的 STARK 證明成本非常低，因為MIMC幾乎是完美地可計算，它的數學形式很簡單。對於平均計算，會包含更少的清晰計算（例如，檢查一個數是大於還是小於另一個），其計算成本可能會更高，會有大約10000-50000倍。