e$BD9J8<:Ni$7$^$9!#e(B
Ruby1.9e$B$G$Ne(BBinaryStringe$B$N<h$j07$$$K$D$$$F<ALd$,$"$j$^$9!#e(B
e$B!Je(Bruby-list e$B$K=P$9$Y$-$G$7$?$G$7$g$&$+!)e(B
e$B=i$a$F%a!<%k$r$9$k$N$GH=CG$,$D$-$^$;$s$G$7$?!#!Ke(B
Ruby1.9e$B$Ne(BStringe$B%/%i%9e(B(e$B0J2<e(BS19e$B$HN,!K$G$O!"e(B
Ruby1.8e$B0JA0$Ne(BStringe$B%/%i%9e(B(S18e$B$HN,!K$G$Ne(B ,
[]=(idx, value)
e$B$N$h$&$J!"e(BSubstringe$B$r2p$7$J$$%P%$%H$NFI$9~$!"e(B
e$B=q$-9~$_$,$G$-$J$/$J$k$N$G$7$g$&$+!)e(B
e$B%a!<%j%s%0%j%9%H$r8+$?$j!"e(BRuby1.9e$B$r%$%s%9%H!<%k$r$7$?$j$7$^$7$?$,!"e(B
e$BAjEv$9$k%a%=%C%I$,8+$D$+$i$J$+$C$?$N$G!“e(B
e$B$J$$$b$N$H2>Dj$7$F0J2<$NOC$rB3$1$^$9!#e(B
e$B!J$”$k$J$i65$($F$$$?$@$1$^$;$s$+!)!Ke(B
e$B%P%$%H$X$N%$%s%G%C%/%9%"%/%;%9$,$G$-$J$$$H$9$k$H!"e(B
S18e$B$G$O2?$NLdBj$b$J$+$C$?<!$N$h$&$JNc$GLdBj$,H/@8$7$^$9!#e(B
=========================================
e$BNc#1!%!J2hA|=hM}!Ke(B
e$B!!!e(B256e$B3,D4$N%0%l!<%9%1!<%k$N%S%C%H%^%C%W2hA|$,e(B
e$B!!!e(BStringe$B%/%i%9$KFI$_9~$^$l$F$$$k$H$9$ke(B
e$B!!!$3$l$KBP$7$F!"NY@$9$k%T%/%;%k$NCM$Ge(B
e$B!!!J?6Q2=$9$k$$+$7A`:n$r9T$&!#e(B(e$B4JC1$N$?$a6-3&$N07$$$O>JN,!Ke(B
e$B!!!e(Bnx, ny = 10, 10
bmp = (0…(nxny)).inject(""){|s,i| s << rand(256); s} #input
data
e$B!!!e(Br = (-1…1)e$B!!e(B# neighbor index
val_x1 = bmp[0,ny] # value[x-1][0…ny]
(1…(nx-1)).each{|x|
e$B!!!e(B val_x1_y1 = bmp[ny(x-1)+0]e$B!!e(B# value[x-1][y-1]
(1…(ny-1)).each{|y|
e$B!!!e(B val_x1_y = val_x1[y] # value[x-1][y]
e$B!!e(Bval_x1[y] =
(r.inject(0){|zx,dx|r.inject(zx){|zy,dy|zy+bmp[ny*(x+dx)+(y+dy)]}}/9.0).to_i
e$B!!!e(Bbmp[ny*(x-1)+(y-1)] = val_x1_y1
e$B!!!#ve(Bal_x1_y1 = val_x1_y
}
val_x1[ny-2] = val_x1_y1
}
bmp[ny*(nx-2)+1,ny-2] = prev_x[1,ny-2]
e$B!!!%S%C%H%^%C%W2hA|$N%G!<%?$Oe(B,e$BDL>oe(B0-255e$B$^$G$N?tCM$r$H$k%Y%/%H%k$H$7$FI=$5$l$^$9!#e(B
e$BMM!9$J2hA|=hM}%"%k%4%j%:%$O$3$N?tCMNs$KBP$7$F%i%s%@%%"%/%;%9$r$7$^$9!#e(B
e$B!!!%P%$%H%"%/%;%9$re(Bbmp_S19[i].ord, bmp_S19[i] = integer.chr
e$B$G9T$&$He(B
e$B!!!e(B(e$B!J%T%/%;%k?t!K#xe(B10e$B8D!KDxEY$N0lJ8;ze(BStringe$B$r@8@.$9$k$3$H$K$J$j$^$9!#e(B
e$B!!!$=$b$=$b?tCMNs$H;W$C$F$$$k$b$N$rItJ,J8;zNs$KJQ49$7$J$1$l$P$J$i$J$$$H$$$&$N$O!"e(B
e$B!!!O@M}E*$K$*$+$7$/!"DL>o$O!"8@8l$N0-MQ$r$7$F$$$k$H$_$J$5$l$k$H;W$$$^$9!#e(B
e$B!!!$=$&;W$&$H$3$N$h$&$JA:n$Oe(BArray#pack,String#unpacke$B$r7PM3$7$Fe(BArraye$B%/%i%9$GA:n$re(B
e$B!!!9T$&$3$H$re(BS19e$B$,6/@)$7$F$$$k$3$H$K$J$j$^$9!#e(B
e$BNc#2!%e(B(e$B%P%$%*%$%s%U%)%^%F%#%/%9!Ke(B
e$B!!!e(B2e$BK$Ne(BDNAe$BG[Ns$N4V$NN;wEYe(B(edit distance)e$B$rF0E*7W2hK!$N0l<oe(B e$B!!!!!!!Je(BNeedleman-Wunsche$B%"%k%4%j%:%!K$G5a$a$ke(B
e$B!!!e(Bgap_score, substitution_score = -3,
Array.new(4){|i|Array.new(4){|j|
(i==j ? 0 : -1)}}
n1, n2 = 10, 10
nuc = “ACGT” # nucleotide (or DNA) character set
dna1, dna2 = [n1, n2].map{|n| (0…n).inject(""){|s,i|s <<
nuc[rand(4)]; s}} # input data
nuc_to_ord = (0…4).inject({}){|h,i|h[nuc[i]]=i; h} # ad hoc
encoding
table
e$B!!!e(B[dna1, dna2].each{|dna| (0…dna.size).each{|i| dna[i] =
nuc_to_ord[dna[i]]}} # dna.encode(“DNA”)
cur_scores = Array.new(n2+1)
prev_scores = Array.new(n2+1){|i| gap_score * i}
(1…n1).each do |i1|
e$B!!!e(Bcur_scores[0] = (gap_score * i1)
e$B!!!e(B(1…n2).each do |i2|
e$B!!!e(B cur_scores[i2] = [prev_scores[i2-1] +
substitution_score[dna1[i1-1]][dna2[i2-1]],
e$B!!!e(B prev_scores[i2] + gap_score,
e$B!!!e(B cur_scores[i2-1] + gap_score
].max
end
end
edit_distance = cur_row_scores[n2]
e$B!!!0lJ8;z$NA^F~!&:o=|$K$Oe(B-3e$B$N%Z%J%k%F%#$rM?$(!“e(B
e$B!!!J8;z$NCV49$Ke(B-1e$B$N%Z%J%k%F%#$rM?$($k$H$7$?$H$-!“e(B
e$B!!!JRJ}$NG[Ns$rJT=8$7$F$b$&JRJ}$NG[Ns$rF@$k$?$a$K:GDcI,MW$J%Z%J%k%F%#$,5a$^$j$^$9!#e(B
e$BNc$,E,Ev$G$J$+$C$?$+$b$7$l$^$;$s$,!“MW$Oe(BDomainSpecifice$B$J%(%s%3!<%G%#%s%0K!$re(B
e$B!!!e(BRubye$B>e$G=q$/$N$K$b?tCM$X$Ne(Bindexe$B%”%/%;%9$Oe(B
e$B!!!=EMW$G$J$$$+$H$$$&$3$H$r$$$$$?$+$C$?$N$G$9!#e(B
e$B???7$7$$%(%s%3!<%G%#%s%0$N9q:]I8=`$,8=$l$k$3$H$O>/$J$/$F$b!“e(B
e$B!!!e(BApplicatione$B!!e(BSpecifice$B$JFH<+e(BEncodinge$B$re(BRubye$B%9%/%j%W%H$G=q$-$?$$$3$H$O$”$k$G$O$J$$$G$7$g$&$+!)e(B
e$B!!!$^$?!”$=$NL\E*$r@55,I=8=$de(Bbytes.eache$B$N$_$G2L$?$9$3$H$Oe(B
e$B!!!Fq$7$$$3$H$b$”$k$N$G$O$J$$$G$7$g$&$+!)e(B
e$B!!!&e(BS19e$B$G$O$3$N$h$&$Je(Bbytee$BNs$N;H$$$+$?$KBP$7$F87$7$$%Z%J%k%F%#$rM?$($F$$$k$H$$$($^$9!#e(B
e$B!!!&$b$A$m$s$3$l$i$NA`:n$Oe(BStringe$B$+$ie(BArray#pack,String#unpacke$B!!$r;H$C$Fe(BArraye$B>e$G9T$&$3$H$b$G$-$^$9!#e(B
e$B!!!&$7$+$7Nc#1!“Nc#2$N$I$A$i$G$bF~NO$N%5%$%:$,?t==!”?tI4e(BMegabytese$B$K$J$k$3$H$Oe(B
e$B!!!DA$7$/$"$j$^$;$s!#e(B
e$B!!!&e(BS18e$B$G$OAGD>$K$+$1$?$N$K$J$s$Ge(BS19e$B$G$3$N$h$&$J5-9fE*$J0z?t$N!Je(Bunpack,pack)
e$B!!%3!<%I$rA^F~$7$J$$$H$$$1$J$$$N$+$H$$$&5$$K$b$J$j$^$9!#e(B
e$B!!!&e(BRubye$B$N7W;;B.EY$G$O!">e$N$h$&$J7W;;$G??$K;H$($k%i%$%V%i%j$O$G$-$J$$$H$$$&0U8+$b$"$k$+$b$7$l$^$;$s!#e(B
e$B!!!$7$+$7!"Nc$(8=;~E@$G%Q%V%j%C%/$J%i%$%V%i%j$H$7$FBQ$($k%9%T!<%I$G$J$/$H$b!"e(B
e$B!!!%W%m%H%?%$%W$D$/$j$d!“e(B
e$B!!!$=$s$J$K%9%1!<%k$NBg$-$/$J$$%W%i%$%Y!<%H$JLdBj$G$N;H$$F;$O$H$F$b9-$$$N$G$O$J$$$G$7$g$&$+!)!!!e(B
e$B!!!e(B(e$B;d$K$H$C$F$O$=$&$G$9!Ke(B
e$B!!!&e(BS18e$B$^$G$N%P%$%H%”%/%;%9$O!"$=$s$J$K$h$/$J$$;EMM$@$C$?$N$G$7$g$&$+!)e(B
e$B!!!&$3$N$h$&$J%P%$%HNs$N07$$J}$G$I$s$J$9$P$i$7$$%"%W%j%1!<%7%g%s$,@8$^$l$k$+$o$+$i$J$$$N$Ke(B
e$B!!!$=$N$h$&$J5!G=$r$4$C$=$j<N$F$F$b$h$$$N$G$7$g$&$+!)e(B
==================================
e$B;d$N0U8+$O!“e(BStringe$B$K$O%P%$%HNs$K%$%s%G%C%/%9$G%i%s%@%`%”%/%;%9$7!"e(B
e$B$=$N?tCM$r%@%$%l%/%H$KFI$_=q$-e(B
e$B$9$k%a%=%C%I$,I,MW$J$N$G$O$J$$$+$H$$$&$b$N$G$9!#e(B
e$B;d$O$3$Ne(B6e$BG/4V$[$I$G!"?tI4$Ne(BRubye$B!!e(BScripte$B$r=q$$$F$-$^$7$?!#e(B
e$B$7$+$7!"%W%m%0%i%_%s%0$K$D$$$F$O$$$^$@AG?M%l%Y%k$G!“e(B
Rubye$B$NFbIt9=B$$b$h$/CN$i$:!“e(B
Encodinge$B$K$D$$$F$b!”$A$g$C$H%0!<%0%k$GD4$Y$?DxEY$G$”$j!"e(B
e$B$I$N$h$&$J;EMM$,$h$$$+$r8@$($kN)>l$G$O$J$$$N$OJ,$+$C$F$$$^$9!#e(B
e$B$G$9$,!"AG?M$J$j$NK=O@$r0J2<$K=R$Y$?$$$H;W$$$^$9!#e(B
e$B;d$K$H$C$F%Y%9%H$J;EMM$O<!$N$h$&$J$b$N$G$9!#e(B
my_best_string[idx] e$B!!e(B #=>
string_S19[i].orde$B!!$rJV$9!#e(B
my_best_string[idx] = integer #=> string_S19[i] =
integer.chr(string_S19.encoding)
e$B!)J8;z!!!e(B e$B!!!e(B #=> e$B!)J8;ze(B.ord
e$BMxE@!'e(B
e$B#0!%%P%$%HNs$r?tCMNs$H;W$C$?$H$-:G$b<+A3!#e(B
e$B!!#1!%e(BASCIIe$BJ8;zNs!"%P%$%J%jNs$N>l9g$Ke(BS18e$B$H2?$NJQ2=$b$J$$!!e(B
e$B!!!e(BS18e$B$r<+A3$Ke(BEncodinge$BBP1~$K$7$?$b$N$H;W$($k!#e(B
e$B!!#2!%J8;z$Ne(Bordinale$B$,e(BFixnume$B$K<}$^$k8B$jJ8;z$NHf3S$,9bB.!J?dB,!Ke(B
e$B!!#3!%%9%/%j%W%H$Ne(BEncodinge$B$,J8;zNs$Ne(BEncodinge$B$HEy$7$/e(B
e$B!!!$J$1$l$P7k6IJ8;zNsCf$G$b?t$G;XDj$7$J$1$l$P$J$i$J$$!#e(B"\u{0x…}"
e$B!J#4e(B.e$B!Ke(BEncodinge$B$,e(BASCIIe$B$G$J$$$H$-%i%s%@%`%"%/%;%9$G$J$$e(B(e$BB?J,!K$H$$$&$N$Oe(BS19e$B$G$bF1$8$J$N$GLdBj$J$$e(B
e$B7gE@!'e(B
e$B!!#1!%J8;z$r@0?tCM$K$7$?$H$-e(BEncodinge$B>pJs$r<:$&$N$GJ#?te(BEncodinge$B$,:.$6$k$H$-0BA4$G$J$$!#e(B
e$B!!!e(B=>e$B!&0BA4@-$,5?$o$l$k$H$-$O!"0lJ8;ze(BStringe$B$r;H$($P$h$$$N$G$O$J$$$G$7$g$&$+!)e(B
e$B!!!&?dB,$G$9$,!"e(Bhexe$B$N?tCM$rD>@\07$&J}$,%W%m8~$1$J$N$G$O$J$$$G$7$g$&$+!)e(B
e$B!!!e(BRubye$B$O%W%m8~$1$K==J,$JG[N8$,$J$5$l$k$O$:$G$9!#e(B
e$B!!!&e(BEncodinge$B$K$D$$$F>$7$/$J$$$N$G!":,K\E*$JLdBj$,$"$k$N$+$b$7$l$^$;$s$,e(B…
e$B!!!Je(Bcharacter_string.ord.chr(character_string.encoding)e$B$,0l0U$G$J$$$H$+e(B…
ord e$B$NCM$,e(Bascii-7bite$BJ8;zItJ,$Ge(Bincompatible
e$B$Je(BEncodinge$B$,$"$k$H$+e(B…e$B!)e(B)
e$B!!!&J8;z%j%F%i%k$r=q$-$K$/$/$J$k!)!!$7$+$7!"=jA’!!!)J8;z!!$H!!e(B"e$BJ8;z!I$O0l;z$7$+0c$$$^$;$s!#e(B
e$B!!!&$=$l$Ke(BS18e$B$^$G$K$=$s$J$KB?$/$NLdBj$,$"$C$?$N$G$7$g$&$+!)e(B
e$B!!!e(B
e$B!&e(BRubye$B$N$b$C$H$b=EMW$J1~MQ$O%&%’%V%"%W%j%1!<%7%g%s$J$N$G!"e(B
e$B!!!e(BHTTPe$B$+$i$I$s$Je(BEncodinge$B$NJ8;zNs$,Mh$k$+J,$+$i$J$$>u67$KBP1~$9$k$?$a!"e(B
e$B!!!e(BWebe$B8@8l$H$7$F%(%s%3!<%G%#%s%0$Ne(B"e$B7?e(Be$B0lCW@-!&0BA4@-!I$r=E;k$9$k$N$@$H8@$o$l$l$Pe(B
e$B!!!JV$98@MU$O$J$$$N$G$9$,!#!#!#e(B
e$B!!!$7$+$7!"$=$NBe=~$O;d$K$O$H$F$bBg$-$/;W$($^$9!#e(B
e$B!!#2!%0lJ8;ze(BStringe$B$r<hF@$9$k$N$Ke(Bstring[i]e$B$H=q$-$?$/$J$C$F$7$^$&!#e(B
e$B!!!e(B=>e$B!&;d$be(BRubye$B$rCN$C$?$3$m$O$=$&$G$7$?!#$7$+$7:#$G$O?tCM$rJV$9e(BS18e$B$N;EMM$KG<F@$7!“e(B
e$B!!!e(BRubye$B$i$7$$e(B(e$B$H;d$,>!<j$K;W$C$F$$$k!K7Z2w$5$de(BPragmatice$B$5$,5$$KF~$C$F$$$^$9!#e(B
e$B!!!&e(BString#e$B$N$h$&$JBg;v$J%a%=%C%I$,e(BString#[i,1]e$B$N5!G=E*$J%(%$%j%”%9$G$h$$$b$N$G$7$g$&$+!)e(B
e$B!!!&e(BS19e$B$K$Oe(BString#chre$B$,$"$k$N$G$3$l$r0z?t$D$-$K$7$Fe(Bstr.chr(idx)e$B$J$I$H$9$l$P!"e(B
e$B!!!e(Bstr[idx,1],str[idx…idx]e$B$h$j$O0U?^$,L@3N$K$J$k$+$bCN$l$^$;$s!#e(B
e$B!!#3!%0lJ8;z$r=q$-9~$$N$Ke(Bstring[i]="e$B$"!I$H=q$-$?$/$J$C$F$7$^$&!#e(B e$B!!!!!!e(B=>e$B!&3N$+$K$=$&$+$bCN$l$^$;$s$,!"e(Bstring[i]="e$B$"$$$&$($*!I$J$I$H$NO"B3@-$r9M$($k$H!"e(B e$B!!!!!!!!!!0lJ8;z$NCV$-49$($H$O9M$($i$l$:!"e(B e$B!!!!!!!!!!ItJ,J8;zNs$NCV49!Je(Bstring[i,1]="e$B$"e(B") e$B$H9M$($kJ}$,E,@Z$K;W$o$l$^$9!#e(B e$B$=$l$KHf$Y$k$H!!e(Bstring[i] = integer e$B$NJ}$Oe(B e$B!!!!!!!!!!$^$5$K0lJ8;z$KBP$9$kBeF~$H$$$&0UL#$7$+;}$A$($:$h$jE,@Z$J$N$G$O$J$$$G$7$g$&$+!)e(B e$B!!!!!!!!!&0lJ8;z$N=q$-9~$_$Ke(Bstring[i..i]e$B$de(Bstring[i,1]e$B$r;H$$$?$/$J$$$H$$$&$N$O$"$k$+$b$7$l$^$;$s!#e(B e$B!!!!!!!!!!$7$+$7!"$3$l$O>e$K5s$2$?MxE@$H$N%P%i%s%9$G9M$($k$He(B e$B!!!!!!!!!!$=$l$[$IBg$-$J$b$N$G$O$J$$$N$G$O$J$$$G$7$g$&$+!)e(B e$B!!!!!!!!e(B([]e$B$H$NBP>N@-$r5>@7$K$7$F!"e(B[]=(i,val)e$B$,e(BIntegere$B$He(BStringe$B$NN>J}$Ne(Bvale$B$r<u$1<h$k!!!!!!!!!!!Je(BS18#<<e$B!!$N$h$&$K!K$H$$$&:v$b$"$k$+$bCN$l$^$;$s!K!!#4!%!Ve(Bstring[i]e$B$OJ8;zNs!W$H%Q%V%j%C%/$K$$$C$?0J>e$"$H$K$OLa$l$J$$!#!!!!!!e(B=>e$B!&$*;!$7$7$^$9!#$3$l$O$"$/$^$GAG?M$NK=O@$G$9!#!!!!!!!!!&$7$+$7!"e(BBytee$BNs$N<h$j07$$$K$D$$$F$O!"!!!!!!!!!!$^$@5DO@$,B3$$$F$$$k$h$&$G$9$N$G!"0le_$NK>$_$r$+$1$F!!!!!!!!!!;W$$@Z$C$?0U8+$r=R$Y$5$;$F$$$?$@$$$F$$$^$9!#!!$=$NB>$N0F!'e(BString#ord(idx)e$B!!e(B=>e$B!!?tCM!!!!e(B=>e$B!!!&?tCMNs$H9M$($?$H$-!"e(Bordinale$B$H$$$&L>A0$OITE,@Z$G$O!)!!!!!!!!!&=q$-9~$_$Ke(Bset_ord(idx, value)e$B!!!)e(BString#get(idx), String#set(idx, value) => e$B!&$&!<$s!#$3$&$J$C$?$i;DG0$G$9!#e(B[ByteStrine$B#g$He(BString] e$B$de(B[String:BINARYe$B$He(BStringe$B!'e(BASCII-8BIT]e$B$J$I!"0[$J$k%/%i%9$d>uBV$Ge(B[],[]= e$B$,J8;zNs$rJV$7$?$j?tCM$rJV$7$?$j$9$k$+$,JQ$o$k!#!!!!e(B=>e$B!!!&$I$A$i$N?6$kIq$$$rK>$$+$G!“e(B
str.to_byte_st!
r, str.force_encoding
e$B$J$I$N%3%s%P!<%8%g%s$,!!!F~$jMp$l$k$h$&$K$J$k$N$G$O!)!!!&$I$s$J>uBV$+J,$+$i$s$+$i$H$K$+$/e(Bforce_encodinge$B$9$k!”$H$$$&$h$&$J!!!%W%m%0%i%%s%0$N=,47$,$G$-$?$ie(BRubye$B8@8l$Ne(B
e$B!!!e(BLove/hatee$B!!e(Bratio
e$B$,K=Mn$9$k$N$G$O$J$$$G$7$g$&$+!)8=:$Ne(BRuby1.9e$B$N;EMM$K;j$k$^$G$K$OKDBg$J5DO@$,@Q$_=E$M$i$l$F$$$k$3$H$H;W$$$^$9!#e(Bstring[i]=e$BJ8;zNs$,7hDj$7$?$N$O$:$$$V$s@N$N$3$H$N$h$&$G$=$N7P0^$r%a!<%j%s%0%j%9%H$N%"!<%+%$%V$+$i$O8+$D$1$k$3$H$O$G$-$^$;$s$G$7$?!#;d$NDs0F$7$?$h$&$J$3$H$,$&$^$/$$$+$J$$$3$H$K!“G<F@$N9T$/M}M3$,$”$l$P4JC1$G$h$$$N$G!"@bL@$7$F$$$?$@$1$^$;$s$+!)$=$N$H$-$O!“AGD>$K$”$-$i$a$k$3$H$K$7$^$9!#e(BRuby1.9e$B$O!“e(BEnumeratore$B$J$I$KAG@2$i$7$$5!G=$,$”$je(B,e$B$9$0$K$b;H$$$?$$$N$G$9$,!">e$K=R$Y$?LdBj$N$?$a$K!"0\9T$Ke(Breluctante$B$K$J$C$F$$$^$9!#$I$&$>$h$m$7$/$*4j$$$7$^$9!#e(B