Optimization of Boyer Moore Algorithm

The potentiality of computers pursues to improve rapid pace with novel and existing technologies and concepts. By combining existing technologies with novel concepts can provide innovations. Computer processing power, storage capacity and memory power and parallel processing have been significantly improved. Depending on these kinds of advantages community can develop existing usable algorithms It may cause to enhance usability of them. The community has developed a useful string searching mechanism

String searching is a significant feature of many problems, including text editing, data retrieval and symbol manipulation. The string matching problem consists in finding one or all occurrences of a pattern in a text, where the pattern and the text are strings over some alphabet .In computer science, string searching sometimes known as string matching algorithm. Boyer Moore string searching algorithm, Naive string search algorithm , Rabin –Karp string search algorithm , Finite–state automation based search , Knuth — Morris Pratt algorithm, Gusfield’s Z algorithm are the examples for some string searching algorithms. Among these algorithms Boyer Moore algorithm is more efficient and well designed for large pattern string and large alphabet. It was developed by Robert S. Boyer and J Strother Moore in 1977.

There was a python serial code for Boyer Moore String searching. It took 165.44 seconds for search 1kB size pattern in 74,259 KB text file. It has been used only one thread. That was main thread. Then I thought to enhance the number of threads in python code.

Optimization was developed based on Threads in python. Existing serial python was built by using one main thread. With first effort, except the main thread used two threads for calculation of good suffix rule and bad suffix rule. It took 163.34 seconds for search 1kB size pattern in 74,259 kB text file. It has been used only for two threads for shifting rule calculations and Main thread for searching mechanism.

Then narrow to Bidirectional searching mechanism. It was used six threads. In this case text file has been divided into two files. two threads for calculating the good suffix rule and two threads for calculating the bad suffix rule. main thread divided into two parts, one of thread in main thread used to search for one part of text file and another thread in main thread used to search on another part of the text file. It took more time. It took 152.31 seconds for searching 1kB size pattern in 74,259 kB text file.

Serial Version — https://github.com/dilshandcs/BoyerMoore-Python

Related posts:

When I read about business leadership, rarely do I find a nugget of wisdom so concise and relevant to work as well as the rest of life, as “disagree and commit”. Jeff Bezos, founder and CEO of…

As I have coached and worked with pastors across the country I am continually met with hesitancy when it comes to that simple question. There are a lot of pastors who want to stop talking about their…

Artificial intelligence is impacting the future of virtually every industry and every human being. Artificial intelligence has acted as the main driver of emerging technologies like big data…