Strängsökning användas i stor utsträckning i bioinformatik, IT-säkerhet (nätverksintrångdetektion) och för sökning av en söksträng i en text mm, därför utvecklades senaste åren stort antal söksträng algoritmer. Denna uppsats handlar om praktisk implementering av följande stängsökningsalgoritmer: Brute-force, Boyer-Moore och Knuth-Morris-Pratt algoritmer med syftet att jämföra hur algoritmens effektivitet påverkas av typ av data och storlek på söksträng. Mått på algoritmernas effektivitet är antal jämförelser som algoritmerna utför. Det är tre typer av text som används för tester: slumpmässigt genererad text som innehåller ettor och nollor som tecken, text som representerar DNA sekvens som består av ett alfabet med fyra bokstäver och en text som innehåller tecken från engelska alfabetet. Resultatet visar hur algoritmernas effektivitet ändras med olika typ av data och förklarar vad i algoritmernas operationssätt som ligger bakom de uppmätta resultaten. / String search is widely used in bioinformatics, IT security (network intrusion detection) and for search of a string in a text etc. This project deals with the practical implementationof the following string-search algorithms: Brute-force, Boyer-Moore and Knuth-Morris-Pratt algorithms with the aim of comparing how the algorithm’s efficiency is depending on the typ of the dataset and the search string size. A measure of the algorithm’s efficiency is the number of comparisons performed by the algorithm. There are three types of text used for tests: random text (0 and 1 as characters), text that represents a DNA sequence that consists of an alphabet of four letters and a text that contains characters from the English alphabet. This project makes an evaluation of the algorithm’s result depending on the type of data where the search is performed and depending on the size of search strings.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:mau-45773 |
| Date | January 2021 |
| Creators | Korotetskaya, Ekaterina |
| Publisher | Malmö universitet, Institutionen för datavetenskap och medieteknik (DVMT) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Swedish |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds