Boyer–Moore thuật toán

Trước trí tri thức:Tiền tố hàm số cùng KMP thuật toán.

KMP thuật toán đem tiền tố xứng đôi tin tức dùng tới rồi cực hạn,

Mà BM thuật toán sau lưng cơ bản tư tưởng là thông qua hậu tố xứng đôi đạt được so tiền tố xứng đôi càng nhiều tin tức tới thực hiện càng mau tự phù nhảy chuyển.

Dẫn vào

Tưởng tượng một chút, nếu chúng ta hình thức tự phù xuyến,Bị đặt ở văn bản tự phù xuyếnTay trái ngẩng đầu lên bộ, sử chúng nó cái thứ nhất tự phù đối tề.

\begin{aligned} \textit{pat}:\qquad\qquad &\texttt{EXAMPLE} \\ \textit{string}:\qquad\quad &\texttt{HERE IS A SIMPLE EXAMPLE} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned}

Ở chỗ này làm định nghĩa, sau này không lắm lời:

Chiều dài vì,Đặc biệt mà đối với từ 0 bắt đầu xuyến tới nói, quy địnhVìXuyến cuối cùng một chữ phù vị trí;

Chiều dài,.

Nếu chúng ta đã biếtĐệCái tự phù( cùngCuối cùng một chữ phù đối tề ) suy xét chúng ta có thể được đến cái gì tin tức:

Quan sát 1

Nếu chúng ta biếtCái này tự phù không ởTrung, chúng ta liền không cần suy xétTừĐệCái, đệCái…… ĐệCái tự phù khởi xuất hiện tình huống,, mà có thể trực tiếp đemTrượt xuống dưới độngCái tự phù.

Quan sát 2

Càng giống nhau mà,Nếu xuất hiện ởNhất cuối cùng ( cũng chính là nhất bên phải ) kia một cáiTự phù vị trí là ly cuối cùng đoan kémCái tự phù,

Như vậy liền có thể không cần xứng đôi, trực tiếp đemVề phía sau hoạt độngCái tự phù: Nếu hoạt động khoảng cách thiếu với,Như vậy chỉ liềnCái này tự phù liền vô pháp bị xứng đôi, đương nhiên hình thức tự phù xuyếnCũng liền sẽ không bị xứng đôi.

Bởi vậy trừ phiTự phù có thể cùngCuối cùng cái kia tự phù xứng đôi, nếu khôngMuốn nhảy quaCái tự phù ( tương đương vớiVề phía sau hoạt độngCái tự phù ). Hơn nữa chúng ta có thể được đến một cái tính toánHàm số:

\begin{array}{ll} \textbf{int}\ delta1(\textbf{char}\ char) \\ \qquad \textbf{if}\ \text{char不在pat中 || char是pat上最后一个字符} \\ \qquad\qquad\textbf{return}\ patlen \\ \qquad \textbf{else} \\ \qquad\qquad\textbf{return}\ patlastpos-i\quad\textbf{//}\ \text{i为出现在pat最末尾的那一个char出现的位置，即pat[i]=char} \end{array}

Chú ý: Hiển nhiên cái này biểu chỉ cần tính toán đếnVị trí

Hiện tại giả thiếtCùngCuối cùng một chữ phù xứng đôi tới rồi, chúng ta đây liền nhìn xemTrước một chữ phù cùngĐếm ngược cái thứ hai tự phù hay không xứng đôi:

Nếu là, liền tiếp tục hồi lui thẳng đến toàn bộ hình thức xuyếnHoàn thành xứng đôi ( lúc này chúng ta liền ởThượng thành công được đến một cáiXứng đôi );

Hoặc là, chúng ta cũng có thể sẽ ở xứng đôi xongĐếm ngược đệCái tự phù sau, ở đếm ngược đệCái tự phù thượng thất xứng, lúc này chúng ta liền hy vọng đemVề phía sau hoạt động đến tiếp theo cái khả năng sẽ thực hiện xứng đôi vị trí, đương nhiên chúng ta hy vọng hoạt động đến càng xa càng tốt.

Quan sát 3(a)

ỞQuan sát 2Trung nhắc tới, đương xứng đôi xongĐếm ngượcCái tự phù sau, nếu ở đếm ngược đệCái tự phù thất xứng, vì khiến choTrung thất xứng tự phù cùngThượng đối ứng tự phù đối tề,

Yêu cầu đemVề phía sau hoạt độngCái tự phù, nói cách khác chúng ta hẳn là đem lực chú ý nhìn về phía lúc sauCái tự phù ( cũng chính là nhìn về phíaHoạt động k lúc sau, mạt đoạn cùngĐối tề cái kia tự phù ).

Mà,

Cho nên chúng ta lực chú ý hẳn là dọc theoVề phía sau nhảyCái tự phù.

Nhưng mà, chúng ta có cơ hội nhảy qua càng nhiều tự phù, thỉnh tiếp tục xem đi xuống.

Quan sát 3(b)

Nếu chúng ta biếtKế tiếpCái tự phù cùngCuối cùngCái tự phù xứng đôi, giả thiết cái này tử xuyến vì,

Chúng ta còn biết ởThất xứng tự phùMặt sau là cùngTương xứng đôi tử xuyến, mà nếuĐối ứng thất xứng tự phù phía trước tồn tại,Chúng ta có thể đemTrượt xuống dưới động một khoảng cách,

Khiến cho thất xứng tự phùỞThượng đối ứng tự phù phía trước xuất hiện( hợp lý tái hiện, plausible reoccurrence, dưới cũng tên gọi tắt pr ) cùngĐối tề. NếuThượng có bao nhiêu cái,Dựa theo từ hữu đến tả hậu tố xứng đôi trình tự, lấy cái thứ nhất ( rightmost plausible reoccurrence, dưới cũng tên gọi tắt rpr ).

Giả thiết lúc nàyTrượt xuống dưới độngCái tự phù ( cũng tứcCuối cùng quả nhiênCùng với nhất bên phải hợp lý tái hiện khoảng cách ), như vậy chúng ta lực chú ý hẳn là dọc theoVề phía sau hoạt độngCái tự phù, này đoạn khoảng cách chúng ta xưng là:

Giả địnhVì $subpat=pat[j+1\dots patlastpos]$ ỞThượng thất xứng khi nhất bên phải hợp lý tái hiện vị trí,( nơi này chỉ cấp ra đơn giản định nghĩa, tại hạ văn thuật toán thiết kế chương sẽ có càng chính xác thảo luận ), như vậy hiển nhiên $k=j-rpr(j),\ m=patlastpos-j$ .

Cho nên có:

\begin{array}{ll} \textbf{int}\ delta2(\textbf{int}\ j) \quad\textbf{//}\ \text{j为失配字符在pat上对应字符的位置} \\ \qquad\qquad\textbf{return}\ patlastpos-rpr(j) \\ \end{array}

Vì thế chúng ta ở thất xứng khi, có thể đem đemThượng lực chú ý sau này nhảy qua $\max(delta_1,delta_2)$ Cái tự phù

Quá trình

Mũi tên chỉ hướng thất xứng tự phù:

\begin{aligned} \textit{pat}:\qquad\qquad &\texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \Uparrow \end{aligned}

$\texttt{F}$ Không có xuất hiệnTrung, căn cứQuan sát 1,Trực tiếp xuống phía dưới di độngCái tự phù, cũng chính là 7 cái tự phù:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \, \, \qquad\quad\ \ \ \Uparrow \end{aligned}

Căn cứQuan sát 2,Chúng ta yêu cầu đemXuống phía dưới di động 4 cái tự phù khiến cho đoản hoành tuyến tự phù đối tề:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad \Uparrow \end{aligned}

Hiện tạichar: $\texttt{T}$ Xứng đôi, đemThượng kim đồng hồ tả di một bước tiếp tục xứng đôi:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\quad\ \ \, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\quad\ \, \Uparrow \end{aligned}

Căn cứQuan sát 3(a), $\texttt{L}$ Thất xứng, bởi vì $\texttt{L}$ Không ởTrung, cho nênXuống phía dưới di độngCái tự phù, màThượng kim đồng hồ xuống phía dưới di độngCái tự phù:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\ \ \ \, \, \Uparrow \end{aligned}

Lúc nàyLại một lần xứng đôi tới rồiCuối cùng một chữ phù $\texttt{T}$ ,Thượng kim đồng hồ hướng tả xứng đôi, xứng đôi tới rồi $\texttt{A}$ ,Tiếp tục hướng tả xứng đôi, phát hiện ở tự phù $\texttt{-}$ Thất xứng:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\ \ \,\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\quad\ \ \ \,\, \Uparrow \end{aligned}

Hiển nhiên trực quan thượng xem, lúc này căn cứQuan sát 3(b),ĐemXuống phía dưới di độngCái tự phù, khiến cho hậu tố $\texttt{AT}$ Đối tề, loại này hoạt động có thể đạt đượcKim đồng hồ lớn nhất hoạt động khoảng cách, lúc này,TứcThượng kim đồng hồ trượt xuống dưới động 7 cái tự phù.

Mà từ hình thức hóa logic xem, lúc này, $delta_1=7-1-2=4,\ delta_2=7, \max(delta_1,delta_2)= 7$ ,Như vậy từ logic hình thức thượng duy trì tiến hànhQuan sát 3(b)Nhảy chuyển:

\begin{aligned} \textit{pat}:\qquad\qquad &\qquad\qquad\qquad\qquad\qquad\quad \;\, \texttt{AT-THAT} \\ \textit{string}:\ \ \ \dots\ &\texttt{WHICH-FINALLY-HALTS.--AT-THAT-POINT} \dots \\ &\qquad\ \ \ \; \qquad\qquad\qquad\qquad\qquad\quad \ \ \; \Uparrow \end{aligned}

Hiện tại chúng ta phát hiệnThượng mỗi một chữ phù đều cùngThượng đối ứng tự phù bằng nhau, chúng ta ởThượng tìm được rồi một cáiXứng đôi. Mà chỉ tiêu phí 14 thứ đốiTrích dẫn, trong đó 7 thứ là hoàn thành một cái thành công xứng đôi sở thiết yếu tương đối số lần (), mặt khác 7 thứ làm chúng ta nhảy vọt qua 22 cái tự phù.

Thuật toán thiết kế

Lúc ban đầu xứng đôi thuật toán

Giải thích

Hiện tại xem như vậy một cái lợi dụngCùngTiến hành tự phù xuyến xứng đôi thuật toán:

\begin{array}{ll} i \gets patlastpos. \\ j \gets patlastpos. \\ \textbf{loop}\\ \qquad \textbf{if}\ j < 0 \\ \qquad \qquad \textbf{return}\ i+1 \\ \\ \qquad \textbf{if}\ string[i]=pat[j] \\ \qquad \qquad j \gets j-1 \\ \qquad \qquad i \gets i-1 \\ \qquad \qquad \textbf{continue} \\ \\ \qquad i \gets i+max(delta_1(string[i]), delta_2(j)) \\ \\ \qquad \textbf{if}\ i > stringlastpos \\ \qquad \qquad \textbf{return}\ false \\ \qquad j \gets patlastpos \\ \end{array}

Nếu mặt trên thuật toán $\textbf{return}\ false$ ,Cho thấyKhông ởTrung; nếu phản hồi một con số, tỏ vẻỞTả khởi lần đầu tiên xuất hiện vị trí.

Sau đó làm chúng ta càng tinh tế mà miêu tả hạ tính toán,Sở dựa vàoHàm số.

Căn cứ trước văn định nghĩa,Tỏ vẻ ởThất xứng khi, tử xuyến $subpat=pat[j+1\dots patlastpos]$ ỞNhất bên phải hợp lý tái hiện vị trí.

Nói cách khác yêu cầu tìm được một cái tốt nhất,Khiến cho $pat[k\dots k+patlastpos-j-1]=pat[j+1\dots patlastpos]$ ,Mặt khác muốn suy xét hai loại đặc thù tình huống:

ĐươngKhi, tương đương với ởPhía trước bổ sung một đoạn giả thuyết tiền tố, trên thực tế cũng phù hợpNhảy chuyển nguyên lý.
ĐươngKhi, nếu,Tắc cái này $pat[k\dots k+patlastpos-j-1]$ Không thể làmHợp lý tái hiện. Nguyên nhân làBản thân là thất xứng tự phù, cho nênTrượt xuống dưới độngCái tự phù sau, ở phía sau chuế xứng đôi trong quá trình vẫn cứ sẽ ởChỗ thất xứng.

Còn phải chú ý hai cái hạn chế điều kiện:

.Bởi vì đươngKhi, có,ỞThượng thất xứng tự phù cũng sẽ ởThượng thất xứng.
Suy xét đến,Cho nên quy định.

Quá trình

Bởi vì lý giảiLà thực hiện BoyerMoore thuật toán trung tâm, cho nên chúng ta sử dụng như sau hai cái ví dụ tiến hành kỹ càng tỉ mỉ thuyết minh:

\begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B C X X X A B C} \\ \textit{rpr(j)}:\qquad\quad\ \ &\texttt{5 4 3 2 1 0 2 1 8} \\ \textit{sgn}:\qquad\qquad\ \ &\texttt{- - - - - - - - +} \end{aligned}

Đối với,Vì $\texttt{BCXXXABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(BCXXX)ABC]XXXABC}$ ,Cũng chính là nhất bên phải hợp lý tái hiện vị trí vì -5, tức;

Đối với,Vì $\texttt{CXXXABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[(CXXX)ABC]XXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{XXXABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[(XXX)ABC]XXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{XXABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[(XX)ABC]XXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{XABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[(X)ABC]XXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{ABC}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[ABC]XXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{BC}$ ,Lại bởi vì,TứcTương đương thất xứng tự phù,Cho nên $string[0\dots 2]$ Cũng không phải phù hợp điều kiệnHợp lý tái hiện, cho nên ở nhất bên phải hợp lý tái hiện là $\texttt{[(BC)]ABCXXXABC}$ ,Cho nên;

Đối với,Vì $\texttt{C}$ ,Cùng lý lại bởi vì,Cho nên $string[1\dots 2]$ Cũng không phải phù hợp điều kiệnHợp lý tái hiện, ở nhất bên phải hợp lý tái hiện là $\texttt{[(C)]ABCXXXABC}$ ,Cho nên;

Đối với,Căn cứĐịnh nghĩa,,Được đến.

Hiện tại lại xem một chút một cái khác ví dụ:

\begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B Y X C D E Y X} \\ \textit{rpr(j)}:\qquad\quad\ \ &\texttt{8 7 6 5 4 3 2 1 8} \\ \textit{sgn}:\qquad\qquad\ \ &\texttt{- - - - - - + - +} \end{aligned}

Đối với,Vì $\texttt{BYXCDEYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(BYXCDEYX)]ABYXCDEYX}$ ,Cũng chính là nhất bên phải hợp lý tái hiện vị trí vì -8, tức;

Đối với,Vì $\texttt{YXCDEYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(YXCDEYX)]ABYXCDEYX}$ ,;

Đối với,Vì $\texttt{XCDEYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(XCDEYX)]ABYXCDEYX}$ ,;

Đối với,Vì $\texttt{CDEYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(CDEYX)]ABYXCDEYX}$ ,;

Đối với,Vì $\texttt{DEYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(DEYX)]ABYXCDEYX}$ ,;

Đối với,Vì $\texttt{EYX}$ ,ỞPhía trước nhất bên phải hợp lý tái hiện chỉ có thể là $\texttt{[(EYX)]ABYXCDEYX}$ ,;

Đối với,Vì $\texttt{YX}$ ,Bởi vì $string[2\dots 3]=string[7\dots 8]$ Hơn nữa có $string[6]\neq string[1]$ ,Cho nên ởPhía trước nhất bên phải hợp lý tái hiện là $\texttt{AB[YX]CDEYX}$ ,;

Đối với,Vì $\texttt{X}$ ,Tuy rằngNhưng là bởi vì,Cho nên ởPhía trước nhất bên phải hợp lý tái hiện là $\texttt{[X]ABYXCDEYX}$ ,;

Đối với,Căn cứĐịnh nghĩa,,Được đến.

Đối xứng đôi thuật toán một cái cải tiến

Cuối cùng, thực tiễn trong quá trình suy xét đến tìm tòi trong quá trình phỏng chừng có 80% thời gian dùng ởQuan sát 1Nhảy chuyển thượng, cũng chính làCùngKhông xứng đôi, sau đó nhảy lên toàn bộTiến hành tiếp theo xứng đôi quá trình.

Vì thế, có thể vì thế tiến hành đặc biệt ưu hoá:

Chúng ta định nghĩa một cái:

\begin{array}{ll} \textbf{int}\ delta0(\textbf{char}\ char) \\ \qquad \textbf{if}\ char=pat[patlastpos] \\ \qquad\qquad \textbf{return}\ large\ \ \text{// large为一个整数，需要满足large>stringlastpos+patlen} \\ \qquad \textbf{return}\ delta1(char) \end{array}

DùngThay thế,Được đến cải tiến sau xứng đôi thuật toán:

\begin{array}{ll} i \gets patlastpos \\ \textbf{loop} \\ \qquad\textbf{if} \ i > stringlastpos \\ \qquad\qquad\textbf{return}\ false\\ \\ \qquad\textbf{while}\ i < stringlen \\ \qquad\qquad i \gets i+delta0(string(i)) \ \ \text{// 除非string[i]和pat末尾字符匹配，否则至多向下滑动patlen }\\\ \qquad\textbf{if}\ i \leqslant\ large \qquad\qquad\qquad\qquad \text{//此时表示string上没有一个字符和pat末尾字符匹配}\ \\ \qquad\qquad\textbf{return}\ false\\ \\ \qquad i \gets i-large \\ \qquad j \gets patlastpos. \\ \qquad\textbf{while}\ j \geqslant\ 0 \ and \ string[i]=pat[j]\\ \qquad \qquad j \gets j-1 \\ \qquad \qquad i \gets i-1 \\ \\ \qquad \textbf{if}\ j < 0 \\ \qquad \qquad \textbf{return}\ i+1 \\ \qquad i \gets i+max(delta_1(string[i]), delta_2(j)) \\ \\ \end{array}

Trong đóKhởi đến nhiều trọng tác dụng, một là cùng loại mặt sau giới thiệu Horspool thuật toán tiến hành nhanh chóng hư tự phù nhảy chuyển, nhị là phụ trợ kiểm tra đo lường tự phù xuyến tìm tòi hay không hoàn thành.

Trải qua cải tiến, so với nguyên thuật toán, ở làmQuan sát 1Nhảy chuyển khi không cần mỗi lần tiến hànhDư thừa tính toán, khiến cho ở thông thường tự phù tập hạ tìm tòi tự phù xuyến tính năng có rõ ràng tăng lên.

delta2 xây dựng chi tiết

Dẫn vào

Ở 1977 năm 10 nguyệtCommunications of the ACMThượng, Boyer, Moor luận văn¹Trung chỉ miêu tảTrạng thái tĩnh biểu,

Cấu tạoCụ thể thực hiện thảo luận xuất hiện ở 1977 năm 6 nguyệt Knuth, Morris, Pratt ởSIAM Journal on ComputingThượng chính thức liên hợp phát biểu KMP thuật toán luận văn².

Mộc mạc thuật toán

Ở giới thiệu KnuthXây dựng thuật toán phía trước, căn cứ định nghĩa, chúng ta sẽ có một cái áp dụng với quy mô nhỏ vấn đề mộc mạc thuật toán:

Đối với[0, patlen)Khu gian mỗi một vị tríi,Căn cứsubpatChiều dài xác định này tái hiện vị trí khu gian, cũng chính là[-subpatlen, i];
Khả năng tái hiện vị trí dựa theo từ hữu đến tả tiến hành trục tự phù tương đối, tìm kiếm phù hợpYêu cầu nhất bên phảiTái hiện vị trí;
Cuối cùng đừng quên lệnh.

Thực hiện

usestd::cmp::PartialEq;

pubfnbuild_delta_2_table_naive(p:&[implPartialEq])->Vecusize>{
letpatlen=p.len();
letlastpos=patlen-1;
letmutdelta_2=vec![];

foriin0..patlen{
letsubpatlen=(lastpos-i)asisize;

ifsubpatlen==0{
delta_2.push(0);
break;
}

forjin(-subpatlen..(i+1)asisize).rev(){
// subpat xứng đôi
if(j..j+subpatlen)
.zip(i+1..patlen)
.all(|(rpr_index,subpat_index)|{
ifrpr_index0{
returntrue;
}

ifp[rpr_indexasusize]==p[subpat_index]{
returntrue;
}

false
})
&&(j0||p[(j-1)asusize]!=p[i])
{
delta_2.push((lastposasisize-j)asusize);
break;
}
}
}

delta_2
}

Đặc biệt mà, đối Rust ngôn ngữ đặc tính tiến hành tất yếu mà giải thích, hạ không lắm lời:

usizeCùngisizeLà cùng nội tồn kim đồng hồ cùng byte số vô ký hiệu số nguyên cùng có ký hiệu số nguyên, ở 32 vị cơ thượng tương đương vớiu32Cùngi32,64 vị cơ thượng tương đương vớiu64Cùngi64.
Hướng dẫn tra cứu số tổ, vector, phân vùng khi sử dụngusizeLoại hình con số ( bởi vì ở làm nội tồn thượng tùy cơ phỏng vấn hơn nữa hạ tiêu không thể vì giá trị âm ), cho nên nếu yêu cầu xử lý giá trị âm phải dùngisize,Mà tiến hành hướng dẫn tra cứu khi lại phải dùngusize,Này liền nhìn đến sử dụngasMấu chốt tự tiến hành hai người chi gian hiện thức thay đổi.
impl PartialEqChỉ là dùng làm phiếm hình, có thể đồng thời duy trìUnicodeMã hóacharCùng cơ số haiu8.

Hiển nhiên, nên bạo lực thuật toán thời gian phức tạp độ vì.

Hiệu suất cao thuật toán

Phía dưới chúng ta muốn giới thiệu chính là thời gian phức tạp độ vì,Nhưng là yêu cầu thêm vàoKhông gian phức tạp độ hiệu suất cao thuật toán.

Tuy rằng 1977 năm Knuth đưa ra cái này xây dựng phương pháp, nhưng mà hắn nguyên thủy phiên bản xây dựng thuật toán tồn tại một cái khuyết tật, trên thực tế đối với nào đóSinh ra không ra phù hợp định nghĩa.

Rytter ở 1980 nămSIAM Journal on ComputingThượng phát biểu văn chương³Đối này đưa ra tu chỉnh, dưới làXây dựng thuật toán:

Đầu tiên suy xét đếnĐịnh nghĩa tương đối phức tạp, chúng ta dựa theoTái hiện vị trí tiến hành phân loại, mỗi một loại tiến hành đơn độc xử lý, đây là hiệu suất cao thực hiện mấu chốt ý nghĩ.

Dựa theo tái hiện vị trí từ xa đến gần, cũng chính là chếch đi lượng từ lớn đến tiểu, phân thành như sau mấy loại:

Toàn bộTái hiện vị trí hoàn toàn ởBên trái, tỷ như $\texttt{[(EYX)]ABYXCDEYX}$ ,Lúc này $delta_2(j) = patlastpos\times 2 - j$ ;
Tái hiện có một bộ phận ởBên trái, có một bộ phận làPhần đầu, tỷ như $\texttt{[(XX)ABC]XXXABC}$ ,Lúc này $patlastpos < delta_2(j) < patlastpos\times 2 - j$ ;Chúng ta đemHoàn toàn ởPhần đầu giới hạn tình huống cũng phân loại ở chỗ này ( đương nhiên căn cứ thực hiện cũng có thể phân loại tại hạ biên ), tỷ như $\texttt{[ABC]XXXABC}$ ,Lúc này;
Tái hiện hoàn toàn ởTrung, tỷ như $\texttt{AB[YX]CDEYX}$ ,Lúc này.

Hiện tại tới thảo luận như thế nào hiệu suất cao mà tính toán này ba loại tình huống:

Đệ nhất loại tình huống

Đây là đơn giản nhất tình huống, chỉ cần một lần biến lịch hơn nữa có thể thuận tiện đemKhởi động lại.

Đệ nhị loại tình huống

Chúng ta quan sát khi nào sẽ xuất hiệnTái hiện một bộ phận ởBên trái, một bộ phận làPhần đầu tình huống đâu? Hẳn làNào đó hậu tố cùngNào đó tiền tố bằng nhau,

Tỷ như phía trước ví dụ:

\begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B C X X X A B C} \\ \end{aligned}

Tái hiện $\texttt{[(XX)ABC]XXXABC}$ , $\texttt{XXABC}$ Hậu tố cùng pat tiền tố trung, có bằng nhau, là $\texttt{ABC}$ .

Trên thực tế đối đệ nhị loại cùng loại thứ ba tình huống tính toán mấu chốt đều yêu cầu tiền tố hàm số tính toán cùng cùng ứng dụng

Như vậy chỉ cầnLấy giá trị khiến choBao hàm cái này bằng nhau hậu tố, như vậy liền có thể được đến đệ nhị loại tình huốngTái hiện, đối với ví dụ, chúng ta chỉ cần khiến cho $j \leqslant 5$ ,

Mà đươngKhi, chính làHoàn toàn ởPhần đầu giới hạn tình huống.

Có thể tính toán lúc này:

Thiết lúc này này đối bằng nhau trước sau chuế chiều dài vì $\textit{prefixlen}$ ,Cũng biết,Như vậy ởBên trái bộ phận chiều dài là $subpatlen-\textit{prefixlen}$ ,

Mà $rpr(j) = -(subpatlen-\textit{prefixlen})$ ,Cho nên được đến $delta_2(j) = patlastpos - rpr(j) = patlastpos \times 2 - j - \textit{prefixlen}$ .

Sau đó mặt khả năng sẽ có bao nhiêu đối bằng nhau tiền tố cùng hậu tố, tỷ như:

\begin{aligned} \textit{j}:\qquad\qquad\quad\ \ &\texttt{0 1 2 3 4 5 6 7 8 9} \\ \textit{pat}:\qquad\qquad\ \ &\texttt{A B A A B A A B A A} \\ \end{aligned}

Ở $j\leq2$ Chỗ có $\texttt{ABAABAA}$ , $2< j \leq 5$ Chỗ có $\texttt{ABAA}$ ,Ở $5<j\leq8$ Chỗ có $\texttt{A}$

Knuth thuật toán khuyết tật là chỉ suy xét dài nhất kia một đôi tình huống, nhưng trên thực tế chúng ta muốn suy xét sở hữuHậu tố cùngTiền tố bằng nhau tình huống, cùng cấp với tính toánSở hữu thật hậu tố cùng thật tiền tố bằng nhau tình huống, cũng dựa theo chiều dài từ lớn đến nhỏ,Phân khu gian tính toán bất đồng.

Lợi dụng tiền tố hàm số cùng nghịch hướng vận dụng tính toán tiền tố hàm số trạng thái dời đi phương trình: $j^{(n)} = \pi[j^{(n-1)}-1]$ ,Lấy được đếnSở hữu bằng nhau thật tiền tố cùng thật hậu tố chiều dài. Từ $\pi[patlastpos]$ Bắt đầu làm dài nhất một đôi chiều dài, sau đó thông qua nghịch hướng vận hành trạng thái dời đi phương trình, được đến tiếp theo cái thứ trưởng bằng nhau thật tiền tố cùng thật hậu tố chiều dài.

Như thế liền hoàn thành đệ nhị loại tình huốngTính toán.

Loại thứ ba tình huống

Tái hiện vừa lúc liền ởTrung ( không bao gồmPhần đầu ), cũng chính là dựa theo từ hữu đến tả trình tự, ở $pat[0\dots patlastpos-1]$ Trung tìm kiếm.

Nếu dùng BM thuật toán giải quyết, chúng ta phải tới rồi một cái BM đệ quy thực hiện loại thứ ba tình huống, kết thúc điều kiện là $patlen \leqslant 2$

Hơn nữa căn cứĐịnh nghĩa, tìm đượcTái hiện tiếp theo cái ( cũng chính là bên trái một cái ) tự phù cùng làmHậu tốTiếp theo cái tự phù không thể giống nhau.

Này liền tốt lắm dẫn dắt chúng ta, có thể sử dụng cùng loại với tính toán tiền tố hàm số quá trình tính toán loại thứ ba tình huống, chẳng qua là tả hữu trái lại tiền tố hàm số:

Hai cái kim đồng hồ phân biệt chỉ hướng tử xuyến tả điểm cuối cùng tử xuyến dài nhất công cộng trước sau chuế “Tiền tố” vị trí, từ hữu hướng tả di động, ở phát hiện chỉ hướng hai chữ phù bằng nhau khi tiếp tục di động, lúc này tương đương với “Tiền tố” biến đại;
Đương hai chữ phù không bằng nhau khi, phía trước bằng nhau bộ phận liền thỏa mãnĐối tái hiện yêu cầu, hơn nữa hồi lui chỉ hướng “Tiền tố” vị trí kim đồng hồ thẳng đến cấu thành tân tự phù bằng nhau hoặc là ra ngoài.

Cùng tiền tố hàm số giống nhau, yêu cầu một cái phụ trợ số tổ, dùng cho hồi lui, có thể sử dụng phía trước tính toán đệ nhị loại tình huống sở sinh thành tiền tố số tổ không gian.

Thực hiện

Kể trên thực hiện

usestd::cmp::PartialEq;
usestd::cmp::min;

pubfnbuild_delta_2_table_improved_minghu6(p:&[implPartialEq])->Vecusize>{
letpatlen=p.len();
letlastpos=patlen-1;
letmutdelta_2=Vec::with_capacity(patlen);

// đệ nhất loại tình huống
// delta_2[j] = lastpos * 2 - j
foriin0..patlen{
delta_2.push(lastpos*2-i);
}

// đệ nhị loại tình huống
// lastpos
letpi=compute_pi(p);// tính toán tiền tố hàm số
letmuti=lastpos;
letmutlast_i=lastpos;// chỉ là vì khởi động lại
whilepi[i]>0{
letstart;
letend;

ifi==lastpos{
start=0;
}else{
start=patlen-pi[last_i];
}

end=patlen-pi[i];

forjinstart..end{
delta_2[j]=lastpos*2-j-pi[i];
}

last_i=i;
i=pi[i]-1;
}

// loại thứ ba tình huống
// delata2[j]
letmutj=lastpos;
letmutt=patlen;
letmutf=pi;
loop{
f[j]=t;
whiletpatlen&&p[j]!=p[t]{
// sử dụng min hàm số bảo đảm mặt sau khả năng hồi lui sẽ không bao trùm phía trước số liệu
delta_2[t]=min(delta_2[t],lastpos-1-j);
t=f[t];
}

t-=1;
ifj==0{
break;
}
j-=1;
}

// không có thực tế ý nghĩa, chỉ là vì hoàn chỉnh định nghĩa
delta_2[lastpos]=0;

delta_2
}

Galil quy tắc đối nhiều lần xứng đôi khi nhất hư tình huống cải thiện

Về hậu tố xứng đôi thuật toán nhiều lần xứng đôi vấn đề

Phía trước tìm tòi thuật toán chỉ đề cập đến ởTrung tìm kiếm lần đầu tiênXứng đôi tình huống, mà đối cùng ởTrung tìm kiếm toàn bộXứng đôi tình huống có rất nhiều bất đồng thuật toán ý nghĩ, vấn đề này trung tâm chú ý điểm là:

Như thế nào lợi dụng phía trước xứng đôi thành công tự phù tin tức, đem nhất hư dưới tình huống thời gian phức tạp độ hàng vì tuyến tính.

Ở nguyên thủy thành công xứng đôi sau, đơn giảnKim đồng hồ về phía sau hoạt độngKhoảng cách sau một lần nữa bắt đầu hậu tố xứng đôi, này sẽ dẫn tới nhất hư dưới tình huống trở lạiThời gian phức tạp độ ( dựa theo lệ thường,Vì,Vì,Như trên ).

Tỷ như một cái cực đoan ví dụ:: $\texttt{AAA}$ ,: $\texttt{AAAAA}\dots$ .

Đối này Knuth nói ra một cái phương pháp là dùng một cái “Số lượng hữu hạn” trạng thái tập hợp tới ký lụcChiều dài tự phù, loại này thuật toán bảo đảmThượng mỗi một chữ phù nhiều nhất tương đối một lần, nhưng đại giới là cái này “Số lượng hữu hạn” trạng thái khả năng quy mô cũng không tiểu, đối với một chữ phù lẫn nhau không bằng nhau,Yêu cầu $\dfrac{1}{2}m^{2}+m$ Cái trạng thái.

Phía dưới giới thiệu ý nghĩ đơn giản thả không cần thêm vào dự xử lý chi tiêu Galil thuật toán⁴.

Galil quy tắc

Giả định một cái,Nó là nào đó tử xuyếnLặp lại n thứ cấu thành tự phù xuyến $UUUU\dots$ Tiền tố, như vậy chúng ta xưngVìMột cái chu kỳ.

Tỷ như, $pat: \texttt{ABCABCAB}$ ,Là $\texttt{ABC}$ Lặp lại $\texttt{ABCABCABC}$ Tiền tố, cho nên $\texttt{ABC}$ Chiều dàiChính là cái nàyChu kỳ chiều dài, cũng tứcThỏa mãn.

Ít nhất có được một cái chiều dài vì nó tự thân chu kỳ, chúng ta quy định ngắn nhất chu kỳ vì, $k\leq patlen$ .

Ở tìm tòi trong quá trình, nếu chúng taThành công mà hoàn thành một lần xứng đôi, như vậy y theo chu kỳ đặc điểm, trên thực tế chỉ cần đemVề phía sau hoạt độngCái tự phù, tương đối nàyCái tự phù hay không đối ứng bằng nhau liền có thể trực tiếp phán đoán hay không tồn tạiLại một cái xứng đôi.

Vì tính toán cái này ngắn nhất chu kỳ chiều dài, chúng ta giả thiết đã biếtBằng nhau một đôi tiền tố - hậu tố, thiết chúng nó chiều dài vì $\textit{prefixlen}$ ,Như vậy có $pat[i] = pat[i+(patlen-\textit{prefixlen})]$ .Do đó được đến chiều dài vì $patlen-\textit{prefixlen}$ Chu kỳ,

Khi chúng ta biếtDài nhất kia một đôi bằng nhau tiền tố - hậu tố, chúng ta phải tới rồiNgắn nhất chu kỳ.

Mà dài nhất bằng nhau trước sau chuế chiều dài, $\pi[patlastpos]$ ,Đã ở chúng ta ở tính toánTrong quá trình, cho nên thực tế không cần thêm vào dự xử lý thời gian cùng không gian, là có thể đem hậu tố xứng đôi thuật toán nhất hư tình huống thời gian phức tạp độ cải thiện thành tuyến tính.

Kết hợp kể trên ưu hoá BM tìm tòi thuật toán cuối cùng thực hiện

#[cfg(target_pointer_width ="64")]
constLARGE:usize=10_000_000_000_000_000_000;

#[cfg(not(target_pointer_width ="64"))]
constLARGE:usize=2_000_000_000;

pubstructBMPatterna>{
pat_bytes:&'a[u8],
delta_1:[usize;256],
delta_2:Vecusize>,
k:usize// pat ngắn nhất chu kỳ chiều dài
}

impla>BMPatterna>{
//...

pubfnfind_all(&self,string:&str)->Vecusize>{
letmutresult=vec![];
letstring_bytes=string.as_bytes();
letstringlen=string_bytes.len();
letpatlen=self.pat_bytes.len();
letpat_last_pos=patlen-1;
letmutstring_index=pat_last_pos;
letmutpat_index;
letl0=patlen-self.k;
letmutl=0;

whilestring_indexstringlen{
letold_string_index=string_index;

whilestring_indexstringlen{
string_index+=self.delta0(string_bytes[string_index]);
}
ifstring_indexLARGE{
break;
}

string_index-=LARGE;

// nếu string_index phát sinh di động, ý nghĩa từ lần trước thành công xứng đôi sau phát sinh ít nhất một lần thất bại xứng đôi.
// lúc này yêu cầu đem Galil quy tắc lần thứ hai xứng đôi chếch đi lượng về linh.
ifold_string_indexstring_index{
l=0;
}

pat_index=pat_last_pos;

whilepat_index>l&&string_bytes[string_index]==self.pat_bytes[pat_index]{
string_index-=1;
pat_index-=1;
}

ifpat_index==l&&string_bytes[string_index]==self.pat_bytes[pat_index]{
result.push(string_index-l);

string_index+=pat_last_pos-l+self.k;
l=l0;
}else{
l=0;
string_index+=max(
self.delta_1[string_bytes[string_index]asusize],
self.delta_2[pat_index],
);
}
}

result
}
}

Nhất hư tình huống ở thực tiễn trung tính có thể ảnh hưởng

Từ thực tiễn góc độ thượng nói, lý luận thượng nhất hư tình huống cũng không dễ dàng ảnh hưởng tính năng biểu hiện, cho dù là rất nhỏ chỉ có 4 tự phù tập tùy cơ văn bản thí nghiệm hạ loại này nhất hư tình huống ảnh hưởng cũng nhỏ đến khó có thể quan sát.

Cũng bởi vậy nếu không có tốt lắm thiết kế, sử dụng Galil pháp tắc sẽ liên lụy một chút bình quân tính năng biểu hiện, nhưng đối với một ít cực đoan đặc thùCùngTỷ như ví dụ trung:: $\texttt{AAA}$ ,: $\texttt{AAAAA}\dots$ ,Galil quy tắc ứng dụng xác thật sẽ khiến cho tính năng biểu hiện đề cao mấy lần.

Cải tiến thuật toán

Simplified Boyer–Moore thuật toán

BM thuật toán nhất phức tạp địa phương liền ở chỗBiểu ( cũng chính là hảo hậu tố biểu ) xây dựng, mà thực tiễn trung phát hiện, ở giống nhau tự phù tập thượng xứng đôi tính năng chủ yếu dựa vàoBiểu ( cũng chính là hư tự phù biểu ), vì thế xuất hiện gần sử dụngBiểu đơn giản hoá bản BM thuật toán, thông thường tính năng cùng nguyên bản chênh lệch rất nhỏ.

Boyer–Moore–Horspol thuật toán

Horspol thuật toán đồng dạng là căn cứ vào hư tự phù quy tắc, ở cùngĐuôi bộ đối tề tự phù thượng ứng dụng.Hiệu quả cùng loại với đối nguyên bản xứng đôi thuật toán cải tiến, thông thường tính năng trội hơn nguyên bản bổn.

Thực hiện

pubstructHorspoolPatterna>{
pat_bytes:&'a[u8],
bm_bc:[usize;256],
}

impla>HorspoolPatterna>{
//...
pubfnfind_all(&self,string:&str)->Vecusize>{
letmutresult=vec![];
letstring_bytes=string.as_bytes();
letstringlen=string_bytes.len();
letpat_last_pos=self.pat_bytes.len()-1;
letmutstring_index=pat_last_pos;

whilestring_indexstringlen{
if&string_bytes[string_index-pat_last_pos..string_index+1]==self.pat_bytes{
result.push(string_index-pat_last_pos);
}

string_index+=self.bm_bc[string_bytes[string_index]asusize];
}

result
}
}

Boyer–Moore–Sunday thuật toán

Sunday thuật toán đồng dạng là lợi dụng hư tự phù quy tắc, chẳng qua so sánh với Horspool nó càng tiến thêm một bước, trực tiếp chú ýĐuôi bộ đối tề cái kia tự phù tiếp theo cái tự phù.

Thực hiện nó chỉ cần hơi chút sửa chữaBiểu, tương đương với ởChiều dàiThượng tiến hành xây dựng.

Sunday thuật toán thông thường dùng làm trong tình huống bình thường thực hiện đơn giản nhất hơn nữa bình quân biểu hiện tốt nhất chi nhất thực dụng thuật toán, thông thường tính năng so Horspool cùng BM muốn hảo một chút.

Thực hiện

pubstructSundayPatterna>{
pat_bytes:&'a[u8],
sunday_bc:[usize;256],
}

impla>SundayPatterna>{
//...
fnbuild_sunday_bc(p:&'a[u8])->[usize;256]{
letmutsunday_bc_table=[p.len()+1;256];

foriin0..p.len(){
sunday_bc_table[p[i]asusize]=p.len()-i;
}

sunday_bc_table
}

pubfnfind_all(&self,string:&str)->Vecusize>{
letmutresult=vec![];
letstring_bytes=string.as_bytes();
letpat_last_pos=self.pat_bytes.len()-1;
letstringlen=string_bytes.len();
letmutstring_index=pat_last_pos;

whilestring_indexstringlen{
if&string_bytes[string_index-pat_last_pos..string_index+1]==self.pat_bytes{
result.push(string_index-pat_last_pos);
}

ifstring_index+1==stringlen{
break;
}

string_index+=self.sunday_bc[string_bytes[string_index+1]asusize];
}

result
}
}

BMHBNFS thuật toán

Nên thuật toán kết hợp Horspool cùng Sunday, là CPython thực hiệnstringlibMô khối khi dùng đếnfindThuật toán⁵,Dưới tên gọi tắt B5S.

B5S cơ bản ý nghĩ là:

Dựa theo hậu tố xứng đôi ý nghĩ, đầu tiên tương đốiVị trí đối ứng tự phù hay không bằng nhau, nếu bằng nhau liền tương đối $0\dots patlastpos-1$ Đối ứng vị trí tự phù hay không bằng nhau, nếu vẫn cứ bằng nhau, như vậy liền phát hiện một cái xứng đôi;
Nếu bất luận cái gì một cái giai đoạn phát sinh không xứng đôi, liền tiến vào nhảy chuyển giai đoạn;
Ở nhảy chuyển giai đoạn, đầu tiên quan sátVị trí tiếp theo cái tự phù hay không ởTrung, nếu không ở, trực tiếp hướng hữu hoạt động,Đây là Sunday thuật toán lớn nhất lợi dụng;
Nếu cái này tự phù ởTrung, đốiChỗ tự phù lợi dụngTiến hành Horspool nhảy chuyển.

Mà căn cứ thời gian tiết kiệm vẫn là không gian tiết kiệm vì mục tiêu đệ nhất, thuật toán sẽ có khác biệt thật lớn bất đồng thực hiện.

Thời gian tiết kiệm phiên bản

Thực hiện

pubstructB5STimePatterna>{
pat_bytes:&'a[u8],
Alpha bet:[bool;256],
bm_bc:[usize;256],
k:usize
}

impla>B5STimePatterna>{
pubfnnew(pat:&'astr)->Self{
assert_ne!(pat.len(),0);

letpat_bytes=pat.as_bytes();
let(Alpha bet,bm_bc,k)=B5STimePattern::build(pat_bytes);

B5STimePattern{pat_bytes,Alpha bet,bm_bc,k}
}

fnbuild(p:&'a[u8])->([bool;256],[usize;256],usize){
letmutAlpha bet=[false;256];
letmutbm_bc=[p.len();256];
letlastpos=p.len()-1;

foriin0..lastpos{
Alpha bet[p[i]asusize]=true;
bm_bc[p[i]asusize]=lastpos-i;
}

Alpha bet[p[lastpos]asusize]=true;

(Alpha bet,bm_bc,compute_k(p))
}

pubfnfind_all(&self,string:&str)->Vecusize>{
letmutresult=vec![];
letstring_bytes=string.as_bytes();
letpat_last_pos=self.pat_bytes.len()-1;
letpatlen=self.pat_bytes.len();
letstringlen=string_bytes.len();
letmutstring_index=pat_last_pos;
letmutoffset=pat_last_pos;
letoffset0=self.k-1;

whilestring_indexstringlen{
ifstring_bytes[string_index]==self.pat_bytes[pat_last_pos]{
if&string_bytes[string_index-offset..string_index]==&self.pat_bytes[pat_last_pos-offset..pat_last_pos]{
result.push(string_index-pat_last_pos);

offset=offset0;

// Galil rule
string_index+=self.k;
continue;
}
}

ifstring_index+1==stringlen{
break;
}

offset=pat_last_pos;

if!self.Alpha bet[string_bytes[string_index+1]asusize]{
string_index+=patlen+1;// sunday
}else{
string_index+=self.bm_bc[string_bytes[string_index]asusize];// horspool
}
}

result
}
}

Nên phiên bản B5S tính năng biểu hiện phi thường lý tưởng, trước mắt trước giới thiệu hậu tố xứng đôi hệ liệt thuật toán trung là trong tình huống bình thường là nhanh nhất.

Không gian tiết kiệm phiên bản

Đồng dạng ở CPythonstringlibTrung thực hiện, sử dụng hai cái số nguyên xấp xỉ thay thế được tự phù biểu cùngTác dụng, cực đại mà tiết kiệm không gian:

Dùng một cái đơn giản Bloom lọc khí thay thế được tự phù biểu ( Alpha bet )

Thực hiện

pubstructBytesBloomFilter{
mask:u64,
}

implBytesBloomFilter{
pubfnnew()->Self{
SimpleBloomFilter{
mask:0,
}
}

fninsert(&mutself,byte:&u8){
(self.mask)|=1u64(byte&63);
}

fncontains(&self,char:&u8)->bool{
(self.mask&(1u64(byte&63)))!=0
}
}

Bloom lọc khí thiết thiết kế thông qua hy sinh chuẩn xác suất ( thực tế còn có vận hành thời gian ) tới cực đại mà tiết kiệm tồn trữ không gianSetLoại hình số liệu kết cấu, nó đặc điểm là sẽ đem tập hợp trung không tồn tại hạng ngộ phán vì tồn tại ( False Positives, tên gọi tắt FP ), nhưng sẽ không đem tập hợp trung tồn tại hạng phán đoán vì không tồn tại ( False Negatives, tên gọi tắt FN ), bởi vậy sử dụng nó khả năng sẽ bởi vì FP mà không có được đến lớn nhất tự phù nhảy chuyển, nhưng sẽ không bởi vì FN mà nhảy qua bổn ứng xứng đôi tự phù.

Lý luận thượng phân tích, kể trên “Bloom lọc khí” thực hiện ởChiều dài ở 50 cái Bytes khi, FP xác suất ước vì 0.5, màChiều dài ở 10 cái Bytes khi, FP xác suất ước vì 0.15.

Tuy rằng này không phải một cái tiêu chuẩn Bloom lọc khí, đầu tiên nó trên thực tế không có sử dụng một cái chân chính ha hi hàm số, trên thực tế nó chỉ là một chữ phù chiếu rọi, đem 0-255 byte chiếu rọi vì nó trước sáu vị cấu thành số.

Nhưng suy xét đến chúng ta ở bên trong tồn thượng tiến hành tự phù tìm tòi, loại này đơn giản hoá liền trọng yếu phi thường, cho dù dùng trước mắt đã biết nhanh nhất phi mã hóa ha hi thuật toánxxHash,Tính toán sở yêu cầu thời gian vẫn so nó cao một số lượng cấp.

Mặt khác đương pat ở 30 byte dưới khi, vì đạt tới tốt nhất FP xác suất, yêu cầu không ngừng một cái ha hi hàm số. Nhưng làm như vậy ý nghĩa không lớn, bởi vì dùng trang có hai cáiu128Con số số tổ cũng đã có thể xây dựng tự phù biểu toàn tự phù tập.

Sử dụngThay thế toàn bộ

Quan sát,Nhất thường sử dụng chỗ chính là hậu tố xứng đôi khi cái thứ nhất tự phù liền không xứng đôi là nhất thường thấy không xứng đôi tình huống, vì thế lệnhskip = delta1(pat[patlastpos]),

Ở đệ nhất giai đoạn không xứng đôi khi, trực tiếp trượt xuống dưới độngskipCái tự phù; nhưng đương đệ nhị giai đoạn không xứng khi, bởi vì khuyết thiếu toàn bộTin tức, chỉ có thể trượt xuống dưới động một chữ phù.

Thực hiện

pubstructB5SSpacePatterna>{
pat_bytes:&'a[u8],
Alpha bet:BytesBloomFilter,
skip:usize,
}

impla>B5SSpacePatterna>{
pubfnnew(pat:&'astr)->Self{
assert_ne!(pat.len(),0);

letpat_bytes=pat.as_bytes();
let(Alpha bet,skip)=B5SSpacePattern::build(pat_bytes);

B5SSpacePattern{pat_bytes,Alpha bet,skip}
}

fnbuild(p:&'a[u8])->(BytesBloomFilter,usize){
letmutAlpha bet=BytesBloomFilter::new();
letlastpos=p.len()-1;
letmutskip=p.len();

foriin0..p.len()-1{
Alpha bet.insert(&p[i]);

ifp[i]==p[lastpos]{
skip=lastpos-i;
}
}

Alpha bet.insert(&p[lastpos]);

(Alpha bet,skip)
}

pubfnfind_all(&self,string:&'astr)->Vecusize>{
letmutresult=vec![];
letstring_bytes=string.as_bytes();
letpat_last_pos=self.pat_bytes.len()-1;
letpatlen=self.pat_bytes.len();
letstringlen=string_bytes.len();
letmutstring_index=pat_last_pos;

whilestring_indexstringlen{
ifstring_bytes[string_index]==self.pat_bytes[pat_last_pos]{
if&string_bytes[string_index-pat_last_pos..string_index]==&self.pat_bytes[..patlen-1]{
result.push(string_index-pat_last_pos);
}

ifstring_index+1==stringlen{
break;
}

if!self.Alpha bet.contains(&string_bytes[string_index+1]){
string_index+=patlen+1;// sunday
}else{
string_index+=self.skip;// horspool
}
}else{
ifstring_index+1==stringlen{
break;
}

if!self.Alpha bet.contains(&string_bytes[string_index+1]){
string_index+=patlen+1;// sunday
}else{
string_index+=1;
}
}

}

result
}
}

Cái này phiên bản thuật toán tương so với phía trước hậu tố xứng đôi thuật toán không đủ mau, nhưng chênh lệch không lớn, tính năng vẫn cứ trội hơn KMP, đến ích với nó nhiều nhất hai cáiu64Số nguyên ưu tú không gian phức tạp độ.

Lý luận phân tích

Dưới là giống nhau tự phù tập hạ các thuật toán biểu hiện, tung độ cùng loại với chấp hành chi tiêu ( cost chỉ xứng đôi thành công m cái tự phù sau thất xứng khi đại giới, skip chỉ phát sinh thất xứng khi trượt xuống dưới động k cái tự phù xác suất ), càng nhỏ tính năng càng tốt. Tọa độ ngang vì hình thức tự phù xuyến pat chiều dài:

字符串搜索算法性能对比图

Ở nhỏ lại tự phù tập ( DNA {A, C, T, G} kiềm cơ đối danh sách ) trung biểu hiện:

小字符集下字符串搜索算法性能对比图

Tổng thượng, ở trọng đại tự phù tập, tỷ như hằng ngày tìm tòi trong quá trình, BoyerMoore hệ liệt thuật toán ưu việt biểu hiện, trong đó chủ yếu ỷ lạiBiểu thực hiện tự phù nhảy chuyển;

Về phương diện khác, ở nhỏ lại tự phù tập,Dưới tác dụng hàng, màTác dụng được đến thể hiện.

Nếu có nhất định giàu có không gian dưới tình huống, hoàn chỉnh không gian phức tạp độ vìBoyerMoore thuật toán càng thêm thông dụng, tổng hợp biểu hiện tối ưu.

Tham khảo tư liệu cùng chú thích

Bổn giao diện gần nhất đổi mới:2024/9/30 17:33:48,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:minghu6,c0nstexpr,CCXXXI,Chrogeek,Early0v0,Enter-tainer,githuu5y5u,iamtwz,ksyx,megakite,Tiphereth-A,wineee,Xeonacid
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng