次のコードは、FMcのコードが機能しないことを示しています。
この行
from name_of_file import olding_the_new,findingは、この質問に対するこのスレッドの私の個人的な回答の私のコードを参照しています。
*name_of_file私のコードのスクリプトを含むファイルに名前を付けます（このスレッドの他の回答にあります）。実行されます。
* または、私のコードをコピーして貼り付けるのが面倒な場合は、インポートのこの行をコメントするだけで、次のコードが実行されますolding_the_new。finding
私はFMcのコードの結果を検証するために 2 つの方法を使用しました:
-1/ 彼のコードによって返されたスパンを'f' のインデックスと'r' のインデックスと比較します。
私のコードによって返された最初のスパンと比較すると、foobar -2/のもの以外にfとrはありません。したがって、上記のインポートが必要です
name_of_file
のたベネ
disp = Noneが に変更された場合disp == True、実行はアルゴリズムを理解するのに役立つ中間結果を表示します。
.
import re
from name_of_file import olding_the_new,finding
def main():
# Two versions of the text: the original,
# and one without any of the "#" markers.
for text_orig in ('BLAH ##BLAH fo####o##ba###r## BL##AH',
'jkh##jh#f',
'#f#oo##ba###r##',
'a##xf#oo##ba###r##',
'ax##f#oo##ba###r##',
'ab###xyf#oo##ba###r##',
'abx###yf#oo##ba###r##',
'abxy###f#oo##ba###r##',
'iji#hkh#f#oo##ba###r##',
'mn##pps#f#oo##ba###r##',
'mn##pab###xyf#oo##ba###r##',
'lmn#pab###xyf#oo##ba###r##',
'fo##o##ba###r## aaaaaBLfoob##arAH',
'fo#o##ba####r## aaaaaBLfoob##ar#AH',
'f##oo##ba###r## aaaaaBLfoob##ar',
'f#oo##ba####r## aaaaBL#foob##arAH',
'f#oo##ba####r## aaaaBL#foob##ar#AH',
'foo##ba#####r## aaaaBL#foob##ar',
'#f#oo##ba###r## aaaBL##foob##arAH',
'#foo##ba####r## aaaBL##foob##ar#AH',
'#af#oo##ba##r## aaaBL##foob##ar',
'##afoo##ba###r## aaaaaBLfoob##arAH',
'BLAHHfo##o##ba###r aaBLfoob##ar#AH',
'BLAH#fo##o##ba###r aaBLfoob##ar',
'BLA#Hfo##o##ba###r###BLfoob##ar',
'BLA#Hfo##o##ba###r#BL##foob##ar',
):
text_clean = text_orig.replace('#', '')
# Collect data on the positions and widths
# of the markers in the original text.
rgx = re.compile(r'#+')
markers = [(m.start(), len(m.group()))
for m in rgx.finditer(text_orig)]
# Find the location of the search phrase in the cleaned text.
# At that point you'll have all the data you need to compute
# the span of the phrase in the original text.
search = 'foobar'
try:
i = text_clean.index(search)
print ('text_clean == %s\n'
"text_clean.index('%s')==%d len('%s') == %d\n"
'text_orig == %s\n'
'markers == %s'
% (text_clean,
search,i,search,len(search),
text_orig,
markers))
S,E = compute_span(i, len(search), markers)
print "span = (%d,%d) %s %s %s"\
% (S,E,
text_orig.index('f')==S,
text_orig.index('r')+1==E,
list(finding(search,text_orig,'#+')))
except ValueError:
print ('text_clean == %s\n'
"text_clean.index('%s') ***Not found***\n"
'text_orig == %s\n'
'markers == %s'
% (text_clean,
search,
text_orig,
markers))
print '--------------------------------'
.
def compute_span(start, width, markers):
# start and width are in expurgated text
# markers are in original text
disp = None # if disp==True => displaying of intermediary results
span_start = start
if disp:
print ('\nAt beginning in compute_span():\n'
' span_start==start==%d width==%d'
% (start,width))
for s, w in markers: # s and w are in original text
if disp:
print ('\ns,w==%d,%d'
' s+w-1(%d)<start(%d) %s'
' s(%d)==start(%d) %s'
% (s,w,s+w-1,start,s+w-1<start,s,start,s==start))
if s + w - 1 < start:
#mwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmmwmwmwmwmwm
# the following if-else section is justified to be used
# only after correction of the above line to this one:
# if s+w-1 <= start or s==start:
#mwmwmwmwmwmwmwmwmwmwmwmwmwmwmwm
if s + w - 1 <= start and disp:
print ' 1a) s + w - 1 (%d) <= start (%d) marker at left'\
% (s+w-1, start)
elif disp:
print ' 1b) s(%d) == start(%d)' % (s,start)
#mwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmwmmwmwmwmwmwm
# Situation: marker fully to left of our text.
# Adjust our start points rightward.
start += w
span_start += w
if disp:
print ' span_start == %d start, width == %d, %d' % (span_start, start, width)
elif start + width - 1 < s:
if disp:
print (' 2) start + width - 1 (%d) < s (%d) marker at right\n'
' break' % (start+width-1, s))
# Situation: marker fully to the right of our text.
break
else:
# Situation: marker interrupts our text.
# Advance the start point for the remaining text
# rightward, and reduce the remaining width.
if disp:
print " 3) In 'else': s - start == %d marker interrupts" % (s - start)
start += w
width = width - (s - start)
if disp:
print ' span_start == %d start, width == %d, %d' % (span_start, start, width)
return (span_start, start + width)
.
main()
結果
>>>
text_clean == BLAH BLAH foobar BLAH
text_clean.index('foobar')==10 len('foobar') == 6
text_orig == BLAH ##BLAH fo####o##ba###r## BL##AH
markers == [(5, 2), (14, 4), (19, 2), (23, 3), (27, 2), (32, 2)]
span = (12,26) True False [(12, 27)]
--------------------------------
text_clean == jkhjhf
text_clean.index('foobar') ***Not found***
text_orig == jkh##jh#f
markers == [(3, 2), (7, 1)]
--------------------------------
text_clean == foobar
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == #f#oo##ba###r##
markers == [(0, 1), (2, 1), (5, 2), (9, 3), (13, 2)]
span = (0,11) False False [(1, 13)]
--------------------------------
text_clean == axfoobar
text_clean.index('foobar')==2 len('foobar') == 6
text_orig == a##xf#oo##ba###r##
markers == [(1, 2), (5, 1), (8, 2), (12, 3), (16, 2)]
span = (2,16) False True [(4, 16)]
--------------------------------
text_clean == axfoobar
text_clean.index('foobar')==2 len('foobar') == 6
text_orig == ax##f#oo##ba###r##
markers == [(2, 2), (5, 1), (8, 2), (12, 3), (16, 2)]
span = (2,15) False False [(4, 16)]
--------------------------------
text_clean == abxyfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == ab###xyf#oo##ba###r##
markers == [(2, 3), (8, 1), (11, 2), (15, 3), (19, 2)]
span = (4,19) False True [(7, 19)]
--------------------------------
text_clean == abxyfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == abx###yf#oo##ba###r##
markers == [(3, 3), (8, 1), (11, 2), (15, 3), (19, 2)]
span = (4,18) False False [(7, 19)]
--------------------------------
text_clean == abxyfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == abxy###f#oo##ba###r##
markers == [(4, 3), (8, 1), (11, 2), (15, 3), (19, 2)]
span = (4,19) False True [(7, 19)]
--------------------------------
text_clean == ijihkhfoobar
text_clean.index('foobar')==6 len('foobar') == 6
text_orig == iji#hkh#f#oo##ba###r##
markers == [(3, 1), (7, 1), (9, 1), (12, 2), (16, 3), (20, 2)]
span = (7,18) False False [(8, 20)]
--------------------------------
text_clean == mnppsfoobar
text_clean.index('foobar')==5 len('foobar') == 6
text_orig == mn##pps#f#oo##ba###r##
markers == [(2, 2), (7, 1), (9, 1), (12, 2), (16, 3), (20, 2)]
span = (7,18) False False [(8, 20)]
--------------------------------
text_clean == mnpabxyfoobar
text_clean.index('foobar')==7 len('foobar') == 6
text_orig == mn##pab###xyf#oo##ba###r##
markers == [(2, 2), (7, 3), (13, 1), (16, 2), (20, 3), (24, 2)]
span = (9,24) False True [(12, 24)]
--------------------------------
text_clean == lmnpabxyfoobar
text_clean.index('foobar')==8 len('foobar') == 6
text_orig == lmn#pab###xyf#oo##ba###r##
markers == [(3, 1), (7, 3), (13, 1), (16, 2), (20, 3), (24, 2)]
span = (9,24) False True [(12, 24)]
--------------------------------
text_clean == foobar aaaaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == fo##o##ba###r## aaaaaBLfoob##arAH
markers == [(2, 2), (5, 2), (9, 3), (13, 2), (27, 2)]
span = (0,9) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == fo#o##ba####r## aaaaaBLfoob##ar#AH
markers == [(2, 1), (4, 2), (8, 4), (13, 2), (27, 2), (31, 1)]
span = (0,7) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaaaBLfoobar
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == f##oo##ba###r## aaaaaBLfoob##ar
markers == [(1, 2), (5, 2), (9, 3), (13, 2), (27, 2)]
span = (0,11) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == f#oo##ba####r## aaaaBL#foob##arAH
markers == [(1, 1), (4, 2), (8, 4), (13, 2), (22, 1), (27, 2)]
span = (0,8) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == f#oo##ba####r## aaaaBL#foob##ar#AH
markers == [(1, 1), (4, 2), (8, 4), (13, 2), (22, 1), (27, 2), (31, 1)]
span = (0,8) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaaBLfoobar
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == foo##ba#####r## aaaaBL#foob##ar
markers == [(3, 2), (7, 5), (13, 2), (22, 1), (27, 2)]
span = (0,7) True False [(0, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == #f#oo##ba###r## aaaBL##foob##arAH
markers == [(0, 1), (2, 1), (5, 2), (9, 3), (13, 2), (21, 2), (27, 2)]
span = (0,11) False False [(1, 13), (23, 31)]
--------------------------------
text_clean == foobar aaaBLfoobarAH
text_clean.index('foobar')==0 len('foobar') == 6
text_orig == #foo##ba####r## aaaBL##foob##ar#AH
markers == [(0, 1), (4, 2), (8, 4), (13, 2), (21, 2), (27, 2), (31, 1)]
span = (0,12) False False [(1, 13), (23, 31)]
--------------------------------
text_clean == afoobar aaaBLfoobar
text_clean.index('foobar')==1 len('foobar') == 6
text_orig == #af#oo##ba##r## aaaBL##foob##ar
markers == [(0, 1), (3, 1), (6, 2), (10, 2), (13, 2), (21, 2), (27, 2)]
span = (2,10) True False [(2, 13), (23, 31)]
--------------------------------
text_clean == afoobar aaaaaBLfoobarAH
text_clean.index('foobar')==1 len('foobar') == 6
text_orig == ##afoo##ba###r## aaaaaBLfoob##arAH
markers == [(0, 2), (6, 2), (10, 3), (14, 2), (28, 2)]
span = (1,14) False True [(3, 14), (24, 32)]
--------------------------------
text_clean == BLAHHfoobar aaBLfoobarAH
text_clean.index('foobar')==5 len('foobar') == 6
text_orig == BLAHHfo##o##ba###r aaBLfoob##ar#AH
markers == [(7, 2), (10, 2), (14, 3), (27, 2), (31, 1)]
span = (5,14) True False [(5, 18), (23, 31)]
--------------------------------
text_clean == BLAHfoobar aaBLfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == BLAH#fo##o##ba###r aaBLfoob##ar
markers == [(4, 1), (7, 2), (10, 2), (14, 3), (27, 2)]
span = (4,16) False False [(5, 18), (23, 31)]
--------------------------------
text_clean == BLAHfoobarBLfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == BLA#Hfo##o##ba###r###BLfoob##ar
markers == [(3, 1), (7, 2), (10, 2), (14, 3), (18, 3), (27, 2)]
span = (5,14) True False [(5, 18), (23, 31)]
--------------------------------
text_clean == BLAHfoobarBLfoobar
text_clean.index('foobar')==4 len('foobar') == 6
text_orig == BLA#Hfo##o##ba###r#BL##foob##ar
markers == [(3, 1), (7, 2), (10, 2), (14, 3), (18, 1), (21, 2), (27, 2)]
span = (5,14) True False [(5, 18), (23, 31)]
--------------------------------
>>>
.
----------------------------------------------
FMcのコードは非常に微妙で、その原理を理解して修正するのに長い間苦労しました。
アルゴリズムを理解するタスクは誰にでも任せます。FMcのコードを正しく動作させるために必要な修正のみを述べます。
.
最初の修正:
if s + w - 1 < start:
# must be changed to
if s + w - 1 <= start or (s==start):
編集
私の最初の現在の回答では、
私は書いていました... or (s<=start)。
それは私の間違いでした、実際には私は書くつもりでした
.. or (s==start)
この編集に関するNOTA BENE：
このエラーは、 FMcの最初のコードを修正するためにここで説明する 2 つの修正で修正されたコードには何の影響もありませんでした (現在、彼は 2 回変更しているため、最初のコードです)。
実際、コードを 2 つの修正で修正すると、 と で取得した 25 の例すべてで正しい結果が得られtext_origます。
したがって、最初の条件が Falseの場合、True のケースは決して発生しないと考えました。これは、おそらく常に 0 より大きいという事実と、マーカーと非マーカー シーケンスの構成によるその他の理由に基づいています... ..
というわけで、この印象のデモンストレーションを見つけようとしましたが、失敗しました。... or (s <= start)... or (s==start)
s < starts+w-1 <= startw
さらに、私はFMcのアルゴリズム(彼が行った編集の前の最初
のアルゴリズム) さえも理解できないという精神状態に達しました!!
それにもかかわらず、私はこの回答をそのままにして、この回答の最後に、これらの修正が必要な理由を説明しようとする説明を投稿します。しかし、私は警告します: FMc
の最初のアルゴリズムは、2 つの異なる文字列に属するインデックスを比較するため、非常に風変わりで理解しにくいものです。 .そして今、私はそれが理にかなっているかもしれないと確信していません....
.
2 番目の修正::
start += w
width = width - (s - start)
# must be changed to
width -= (s-start) # this line MUST BE before the following one
start = s + w # because start += (s-start) + w
-------------------
間違ったコードを与えているにもかかわらず、2 人が FMc の回答に賛成票を投じたことに唖然としました。これは、指定されたコードをテストせずに回答に賛成票を投じたことを意味します。
--------------------------------------------
.
編集
条件を次のif s + w - 1 < start:ように変更する必要があるのはなぜ
if s + w - 1 <= start or (s==start):ですか?
s + w - 1 < startFalse と一緒にs等しいことが起こる可能性があるため です。
この場合、実行はセクションに移動し、(修正されたコードで) 実行します。 start
else
width -= (s - start)
start = s + w
したがって、width関係するシーケンスを見ると明らかに変化するはずですが、変化しません。
このケースは、次のシーケンスのように、最初のマーカーが検査される瞬間に発生する可能性があります。
'#f#oo##ba###r##' : s,w==0,1 , 0==s==start==0
'ax##f#oo##ba###r##' : s,w==2,2 , 2==s==start==2
'abxy###f#oo##ba###r##' : s,w==4,3 , 4==s==start==4
'#f#oo##ba###r## aaaBL##foob##arAH' : s,w==0,1 , 0==s==start==0
'BLAH#fo##o##ba###r aaBLfoob##ar' : s,w==4,1 4==s==start==4
次のものでは、2 番目のマーカーの検査で発生します。
'iji#hkh#f#oo##ba###r##' : s,w==7,1 , 7==s==start==7
'mn##pps#f#oo##ba###r##' : s,w==7,1 , 7==s==start==7
私のコードを設定して実行すると、よりよく理解できますdisp = True。
がs + w - 1 <= start検証されると、実行がセクションに移動せず、 toと toの追加のみがある最初のセクションに移動するため、 smay equalであることは問題ありません。
しかしis False while equalsの場合、命令の実行がwidthの値に何も変化しないセクションに実行が移ってしまい、それが面倒です。そのため、この宛先を防ぐため
に条件を追加する必要があり、いくつかの例が示すように、False の場合でもこの宛先を防ぐために条件を追加する必要があります。startelsewsstart
s + w - 1 <= startsstartelsewidth -= (s-start)
or (s==start)elseors+w-1 <= start
.
命令を(with =) にs+w-1 < start変更しなければならないのは、 (2 番目のマーカー)
と(1 番目のマーカー)
の場合と同様に、1 文字#のみに対応する
ケースのためです。s+w-1 <= start
w==1
mn##pps#f#oo##ba###r##
BLAH#fo##o##ba###r