pythonデータ構造2の文字列
10544 ワード
pythonデータ構造チュートリアル第2課文字列はコンピュータデータ処理の過程で最も重要であり、最も基礎的な内容でもあり、それをマスターすることは私たちのプログラミングをより効率的で簡潔にするのに役立ちます.
一.简介二.文字列の抽象データ型3.文字列のマッチングアルゴリズム1素朴マッチングアルゴリズム2 KMPマッチングアルゴリズム4.文字列クラスのチェーンテーブル実現5.正規表現1.正規表現とは2.pythonの正規表現
一.概要
コンピュータの分野では、基本的な文字記号を文字、記号のシーケンスを文字列、貧しい文字のセットを文字セット、実際によく使われる文字セットをASCII文字セットまたはUnicode文字セット、python 2と呼ぶ.5以降のデフォルトの文字セットはASCII文字セットです.
二.文字列の抽象データ型(ADT)
1つの文字列タイプにはスライスがあり、ビット単位で要素を取り、文字列の長さを返し、文字列の接合などがあり、その基本ADTは以下の通りである.
前列match(self,str)ではselfをターゲット列,strをモード列と呼ぶ.ここでは、pythonの内部にはすでに完全な文字列タイプstrがあるので、本編では文字列自体のタイプの実装に重点を置いていません.文字列タイプベースの重要な操作とアルゴリズムでは、pythonのstrタイプの一般的な方法を次にリストし、文字列の重要な操作である文字列マッチングを順に紹介します.文字列タイプのチェーンテーブルインプリメンテーションおよびステップアップコンテンツ--正規表現.strクラスの一般的な方法は以下の通りです.
前の列のコードの出力は次のとおりです.
三.文字列の一致アルゴリズム
ここでは、基本的で一般的な素朴なマッチングアルゴリズムと、高度なKMPアルゴリズムの2つを紹介する.素朴マッチングアルゴリズム素朴マッチングアルゴリズムは最も直感的に実行可能な戦略を採用する:1)パターン列とターゲット列を用いて左から右へ文字ごとにマッチングする2)不マッチングを発見した場合,ターゲット列の次の位置がパターン列にマッチングするかどうかを考慮する3)マッチングに成功すればアルゴリズム素朴マッチングアルゴリズムを終了するのは非常に簡単で理解しやすいが,その効率は低い.ここではマッチングアルゴリズムを直接与えます
上記のコードをよく分析すると、その効率が低下する原因は、マッチング中に異なるものに遭遇すると、パターン列がターゲット列の前の次の位置に戻り、そこから再び文字を最初から比較することにあることがわかります.これは,毎回の文字比較を完全に独立した操作と見なし,文字列自体の特徴を全く利用しておらず,前述した文字比較で得られた情報を十分に利用していないことに相当し,ここでは効率的なマッチングアルゴリズムを紹介する.
2.KMPマッチングアルゴリズムは、素朴マッチングアルゴリズムと比較して、KMPマッチングアルゴリズムの効率が本質的に向上し、その主な利点は、素朴マッチングアルゴリズムにおける朔回現象を克服することである.1回のマッチングに失敗した後、パターン列は、ターゲット列の前に戻って次の位置から再開するのではなく、失敗した位置iにとどまり、パターン列の前のある位置kとターゲット列のこの位置とを比較し続け、これにより、前回比較した情報パターン列の各位置iの要素が、自分が失敗した後にジャンプすべき位置kに対応していることを十分に利用することができる.このテーブルをpnextと呼ぶとともに、pnextはターゲット列に関係なく、パターン列自体の情報に基づいて確立することができる.現在、pnextテーブルがあると仮定し、KMPアルゴリズムの関数コードを与える.
上の列のコードの5行目で、判断条件がi==1であるのは、マッチングに失敗した文字が存在する可能性がある前に行ったマッチングに利用価値が含まれていないため、最初から始める必要があるため、pnext[0]に-1を格納します.次に、pnextテーブルの構築について説明します.接尾辞の定義:「abcab」の列があると仮定すると、「a」、「ab」、「abc」、「abca」を母列と呼ぶ接頭辞と、「b」、「ab」、「cab」、「bcab」を母列と呼ぶ接尾辞パターン列における位置kマッチングに失敗した後、回転する位置は、前k-1文字のうち、最も長い等の前接尾辞の大きさに依存し、以上のように‘abcdabcgd’によって確立されたpnext表は,[−1,0,0,−1,0,3,0]ここでは繰返しの思想を用いてpnext表を解く:1)kに位置する要素値がiに位置する要素値と等しい場合,k+1がi+1に等しい場合,k+1に対応するジャンプ位置はi+1のジャンプ位置であり,k+1がi+1に等しくない場合,k+1のジャンプ位置はi+12に対応する)kに位置する要素値とiに位置する要素値が等しくない場合、iの値がpnext[i]3)kにジャンプするのはマッチングエラー位置であり、iは前のk-1要素の最大等しい接尾辞長であり、pnext[0]=-1は上記のステップでpnextの解法関数を得ることができる
次に、KMPアルゴリズムを用いて例を挙げる.
結果:
四.文字列クラスのチェーンテーブル実装
単一チェーンテーブルを使用して文字列クラスを実現すると、文字列の挿入削除操作をより容易に実現できます.次に、チェーンテーブルを使用して実現される文字列クラスのソースコードを提供します.文字列クラスの基本的な方法が含まれています.
例:
結果:
五.正規表現
1.正規表現の正規表現とは、規則式(Regular Expression)とも呼ばれ、通常はregex、regexpまたはREと略記される.正規表現は文字列操作の論理式であり、事前に定義された特定の文字、およびこれらの特定の文字の組み合わせで「規則文字列」を構成する.この「ルール文字列」は、文字列に対するフィルタリングロジックを表すために使用されます.正規表現と別の文字列を指定すると、次のような目的を達成できます.与えられた文字列が正規表現の一致に合致するかどうか 正規表現により、文字列から所望の特定の部分正規表現を取得できる特徴は、 である.柔軟性、論理性、機能性が非常に強い は、文字列の複雑な制御 を極めて簡単な方法で迅速に達成することができる.接触したばかりの人にとって、比較的難解な正規表現は文字列操作における高度で複雑な部分であり、ここではpythonの正規表現と基本応用 のみを簡単に紹介する.
2.pythonの正規表現pythonの正規表現パッケージreは、メタ文字と呼ばれる特殊な文字のセットを規定しており、文字列に一致するときに特殊な役割を果たし、メタ文字は全部で14個あります:^$*+?|{}[]()通常文字列にはエスケープ文字を除き、残りは通常文字であり、reパケットが提供するいくつかの特殊な操作に現れる場合にのみ、これらの文字にはpython reパケットの主な操作があります.
python reパッケージのいくつかのメタ文字について説明したが、次に、各メタ文字の意味を具体的に説明する1)文字群記述子[...]:四角カッコにリストされている任意の文字と一致することを示し、文字のソートは重要ではない[abc]aまたはbまたはcと一致する[0-9 a-zA-Z]が、ある数字とアルファベットa[1-9][0-9]を一致させることができるa 10、a 11、a 12…a 99[^...]表示对^后的文字组求补
2)ドット文字.ドット文字はワイルドカードで、任意の文字a...bに一致し、aで始まるbで終わる任意の4文字に一致することができる.
3)エスケープ文字:エスケープ文字は、一般的に使用される文字グループを定義します.たとえば、dと10進数の一致Dと非10進数のすべての文字の一致sと空白の文字の一致Sと非空白の文字の一致wとアルファベット数の文字の一致
4)繰り返し記述子:パターンaは、マッチングパターンがaの0回または任意の複数回繰り返して一致することを要求する.
取得:
5)オプション記述子:モードa?空の列やaと一致することができます.例えば、-?d+はすべての整数を表すことができる
6)決定回数反復{n}:a{n}とaのn回反復マッチング
7)繰返し回数範囲記述子{m,n}:a{m,n}はaのm回からn回の繰返しと一致することができる
8)選択記述子|:a|b|cは、aまたはbまたはcのいずれかと一致することができることを示す
9)先頭記述子行頭記述子:'^a'は行頭に位置する接頭辞サブ列aとのみ一致する行尾記述子:'$a'は行尾に位置する接尾辞サブ列aとのみ一致する.'A'の先頭のモードは、一致する列全体の接頭辞とのみ一致する.'Z'の終了モードは、一致する列全体の接尾辞とのみ一致する
一.简介二.文字列の抽象データ型3.文字列のマッチングアルゴリズム1素朴マッチングアルゴリズム2 KMPマッチングアルゴリズム4.文字列クラスのチェーンテーブル実現5.正規表現1.正規表現とは2.pythonの正規表現
一.概要
コンピュータの分野では、基本的な文字記号を文字、記号のシーケンスを文字列、貧しい文字のセットを文字セット、実際によく使われる文字セットをASCII文字セットまたはUnicode文字セット、python 2と呼ぶ.5以降のデフォルトの文字セットはASCII文字セットです.
二.文字列の抽象データ型(ADT)
1つの文字列タイプにはスライスがあり、ビット単位で要素を取り、文字列の長さを返し、文字列の接合などがあり、その基本ADTは以下の通りである.
ADT String:
String(self,sseq) # sseq
is_empty(self) #
len(self) #
char(self,index) # index
substr(self,a,b) # [a,b]
match(self,str) # str
concat(self,str) # str
subst(self,str1,str2) # str1 str2
前列match(self,str)ではselfをターゲット列,strをモード列と呼ぶ.ここでは、pythonの内部にはすでに完全な文字列タイプstrがあるので、本編では文字列自体のタイプの実装に重点を置いていません.文字列タイプベースの重要な操作とアルゴリズムでは、pythonのstrタイプの一般的な方法を次にリストし、文字列の重要な操作である文字列マッチングを順に紹介します.文字列タイプのチェーンテーブルインプリメンテーションおよびステップアップコンテンツ--正規表現.strクラスの一般的な方法は以下の通りです.
str1 = str('hello world!') #
str2 = str1[0:6] #
str3 = str2 + str1 #
for char in str3: # yield
print(char, end = '') # str3
print() #
print(len(str3)) #
stra = '**##'
strb = '1111'
strc = strb.join(stra) # ，stra
print(strc)
前の列のコードの出力は次のとおりです.
hello hello world!
18
*1111*1111#1111#
三.文字列の一致アルゴリズム
ここでは、基本的で一般的な素朴なマッチングアルゴリズムと、高度なKMPアルゴリズムの2つを紹介する.素朴マッチングアルゴリズム素朴マッチングアルゴリズムは最も直感的に実行可能な戦略を採用する:1)パターン列とターゲット列を用いて左から右へ文字ごとにマッチングする2)不マッチングを発見した場合,ターゲット列の次の位置がパターン列にマッチングするかどうかを考慮する3)マッチングに成功すればアルゴリズム素朴マッチングアルゴリズムを終了するのは非常に簡単で理解しやすいが,その効率は低い.ここではマッチングアルゴリズムを直接与えます
def naive_matching(t,p):
m,n = len(p),len(t)
i,j = 0,0
while i < m and j < n: #i==m
if p[i] == t[j]: #
i,j = i+1,j+1
else: # t
i,j = 0,j-i+1
if i == m: # ，
return j - i
return -1 # ， -1
上記のコードをよく分析すると、その効率が低下する原因は、マッチング中に異なるものに遭遇すると、パターン列がターゲット列の前の次の位置に戻り、そこから再び文字を最初から比較することにあることがわかります.これは,毎回の文字比較を完全に独立した操作と見なし,文字列自体の特徴を全く利用しておらず,前述した文字比較で得られた情報を十分に利用していないことに相当し,ここでは効率的なマッチングアルゴリズムを紹介する.
2.KMPマッチングアルゴリズムは、素朴マッチングアルゴリズムと比較して、KMPマッチングアルゴリズムの効率が本質的に向上し、その主な利点は、素朴マッチングアルゴリズムにおける朔回現象を克服することである.1回のマッチングに失敗した後、パターン列は、ターゲット列の前に戻って次の位置から再開するのではなく、失敗した位置iにとどまり、パターン列の前のある位置kとターゲット列のこの位置とを比較し続け、これにより、前回比較した情報パターン列の各位置iの要素が、自分が失敗した後にジャンプすべき位置kに対応していることを十分に利用することができる.このテーブルをpnextと呼ぶとともに、pnextはターゲット列に関係なく、パターン列自体の情報に基づいて確立することができる.現在、pnextテーブルがあると仮定し、KMPアルゴリズムの関数コードを与える.
def matching_KMP(t,p,pnext):
j,i = 0,0
n,m = len(t),len(p)
while j < n and i < m: #i==m
if i == -1 or t[j] == p[i]:
j,i = j+1,i+1 #
else: # pnext
i = pnext[i]
if i == m: # ，
return j-i
return -1 # ， -1
上の列のコードの5行目で、判断条件がi==1であるのは、マッチングに失敗した文字が存在する可能性がある前に行ったマッチングに利用価値が含まれていないため、最初から始める必要があるため、pnext[0]に-1を格納します.次に、pnextテーブルの構築について説明します.接尾辞の定義:「abcab」の列があると仮定すると、「a」、「ab」、「abc」、「abca」を母列と呼ぶ接頭辞と、「b」、「ab」、「cab」、「bcab」を母列と呼ぶ接尾辞パターン列における位置kマッチングに失敗した後、回転する位置は、前k-1文字のうち、最も長い等の前接尾辞の大きさに依存し、以上のように‘abcdabcgd’によって確立されたpnext表は,[−1,0,0,−1,0,3,0]ここでは繰返しの思想を用いてpnext表を解く:1)kに位置する要素値がiに位置する要素値と等しい場合,k+1がi+1に等しい場合,k+1に対応するジャンプ位置はi+1のジャンプ位置であり,k+1がi+1に等しくない場合,k+1のジャンプ位置はi+12に対応する)kに位置する要素値とiに位置する要素値が等しくない場合、iの値がpnext[i]3)kにジャンプするのはマッチングエラー位置であり、iは前のk-1要素の最大等しい接尾辞長であり、pnext[0]=-1は上記のステップでpnextの解法関数を得ることができる
def gen_pnext(p):
k,i,m = 0,-1,len(p)
pnext = [-1]*m # -1
while k < m-1:
if i == -1 or p[k] == p[i]: #
i,k = i+1,k+1
if p[k] == p[i]:
pnext[k] = pnext[i]
else:
pnext[k] = i
else:
i = pnext[i]
return pnext
次に、KMPアルゴリズムを用いて例を挙げる.
stra = 'hello! this is KMP_matching'
strb = 'this'
pnext = gen_pnext(strb)
k = matching_KMP(stra,strb,pnext)
print(stra)
print(strb)
print('\"'+strb+'\"'+' in '+'\"'+stra+'\"' +'\'s ' + str(k))
結果:
hello! this is KMP_matching
this
"this" in "hello! this is KMP_matching"'s 7
四.文字列クラスのチェーンテーブル実装
単一チェーンテーブルを使用して文字列クラスを実現すると、文字列の挿入削除操作をより容易に実現できます.次に、チェーンテーブルを使用して実現される文字列クラスのソースコードを提供します.文字列クラスの基本的な方法が含まれています.
import copy #
#
class Node:
def __init__(self,char,next_ = None):
self.char = char
self.next = next_
''' ， 、 、 、 、 、 、KMP 、 '''
class strllist:
def __init__(self,string = None): #
self.head = Node()
if string is None:
self.num = 0
elif string =='':
self.head.char =''
self.num = 1
else:
self.head.char = string[0]
p = self.head
i = 1
while i < len(string):
t = Node(string[i])
p.next = t
p = p.next
i += 1
self.num = len(string)
def __len__(self): #
return self.num
#
def naive_matching(self,string):
p = self.head
q = self.head
m = len(string)
i = 0
k = 1
while p is not None and i < m:
if p.char == string[i]:
p = p.next
i += 1
else:
i = 0
q = q.next
p = q
k += 1
if i == m:
return k
else:
return -1
# i
def go_loc(self,i):
k = 1
p = self.head
while k < i:
p = p.next
k += 1
return p
# stra strb
def replace(self,stra,strb):
while self.naive_matching(stra) != -1:
i = self.naive_matching(stra)
if i == 1:
p = self.go_loc(len(stra)+1)
bllist = strllist(strb)
self.head = bllist.head
q = self.go_loc(len(strb))
q.next = p
else:
p = self.go_loc(i-1)
q = self.go_loc(i+len(stra))
bllist = strllist(strb)
p.next = bllist.head
t = bllist.go_loc(len(strb))
t.next = q
#
def printall(self):
p = self.head
while p is not None:
print(p.char,end = '')
p = p.next
print()
# ， pnext
@staticmethod
def gen_pnext(p):
m = len(p)
pnext = [-1] * m
i,k = 0,-1
while i < m-1:
if k == -1 or p[i] == p[k]:
i,k = i+1,k+1
if p[i] == p[k]:
pnext[i] = pnext[k]
else:pnext[i] = k
else:
k = pnext[k]
return pnext
#KMP
def matching_KMP(self,string,pnext):
p = self.head
m = len(string)
i = 0
k = 1
while p is not None and i < m:
if i == -1 or p.char == string[i]:
i += 1
p = p.next
k += 1
else:
i = pnext[i]
if i == m:
return k - i
return -1
# stra
def remove(self,stra):
while self.naive_matching(stra) != -1:
i = self.naive_matching(stra)
if i == 1:
self.head = self.go_loc(len(stra)+1)
else:
p = self.go_loc(i-1)
q = self.go_loc(i+len(stra))
p.next = q
例:
a = strllist('abcdefg abcdefg')
b = str('a')
a.printall()
a.remove(b)
a.printall()
結果:
abcdefg abcdefg
bcdefg bcdefg
五.正規表現
1.正規表現の正規表現とは、規則式(Regular Expression)とも呼ばれ、通常はregex、regexpまたはREと略記される.正規表現は文字列操作の論理式であり、事前に定義された特定の文字、およびこれらの特定の文字の組み合わせで「規則文字列」を構成する.この「ルール文字列」は、文字列に対するフィルタリングロジックを表すために使用されます.正規表現と別の文字列を指定すると、次のような目的を達成できます.
2.pythonの正規表現pythonの正規表現パッケージreは、メタ文字と呼ばれる特殊な文字のセットを規定しており、文字列に一致するときに特殊な役割を果たし、メタ文字は全部で14個あります:^$*+?|{}[]()通常文字列にはエスケープ文字を除き、残りは通常文字であり、reパケットが提供するいくつかの特殊な操作に現れる場合にのみ、これらの文字にはpython reパケットの主な操作があります.
#
r1 = re.complie(pattern, flag = 0)
# string pattern
re.search(pattern, string, flag = 0)
# string pattern
re.match(pattern,string,flag = 0)
''' pattern string ，maxsplit ，flags = 0 string'''
re.split(pattern, string,maxsplit=0,flags = 0)
python reパッケージのいくつかのメタ文字について説明したが、次に、各メタ文字の意味を具体的に説明する1)文字群記述子[...]:四角カッコにリストされている任意の文字と一致することを示し、文字のソートは重要ではない[abc]aまたはbまたはcと一致する[0-9 a-zA-Z]が、ある数字とアルファベットa[1-9][0-9]を一致させることができるa 10、a 11、a 12…a 99[^...]表示对^后的文字组求补
2)ドット文字.ドット文字はワイルドカードで、任意の文字a...bに一致し、aで始まるbで終わる任意の4文字に一致することができる.
3)エスケープ文字:エスケープ文字は、一般的に使用される文字グループを定義します.たとえば、dと10進数の一致Dと非10進数のすべての文字の一致sと空白の文字の一致Sと非空白の文字の一致wとアルファベット数の文字の一致
4)繰り返し記述子:パターンaは、マッチングパターンがaの0回または任意の複数回繰り返して一致することを要求する.
import re
re.split('a*','abbaaabbbddbbabbaddaaaddaa')
取得:
['', 'bb', 'bbbddbb', 'bb', 'dd', 'dd', '']
5)オプション記述子:モードa?空の列やaと一致することができます.例えば、-?d+はすべての整数を表すことができる
6)決定回数反復{n}:a{n}とaのn回反復マッチング
7)繰返し回数範囲記述子{m,n}:a{m,n}はaのm回からn回の繰返しと一致することができる
8)選択記述子|:a|b|cは、aまたはbまたはcのいずれかと一致することができることを示す
9)先頭記述子行頭記述子:'^a'は行頭に位置する接頭辞サブ列aとのみ一致する行尾記述子:'$a'は行尾に位置する接尾辞サブ列aとのみ一致する.'A'の先頭のモードは、一致する列全体の接頭辞とのみ一致する.'Z'の終了モードは、一致する列全体の接尾辞とのみ一致する