Knowledge base: Warsaw University of Technology

Settings and your account

Back

Estimated comparison of contractors' names using Python language

Eryk Kołodziejczyk

Abstract

In this thesis the point was to write library with methods of estimated comparision of names. Library was written in high – level programming language, Python. Problem of approximated string matching is one of a contemporary challenges of todays’ information technology. This science field is used to explore written and also spoken text, e.g. in voice recognition. Comparing inscriptions is task for science experimenters, like in matching of DNA sequences, and also in business projects, like point of this diploma work, comparison of contactors’ names. Created solution compares a pair of titles by calculating distance coefficient. When names are the same, it equals 1, and if they are totally different, it equals 0. In the library are collected Hamming, Levenshtein, Jaro, Jaro – Winkler and Ratcliff – Obershelp methods. These methods are different in structure, way of calculating distance coefficient and performance. Created library was tested on database of conractors’ names, which were mutated in different ways. The original list was compared with damaged, end every of names pair was calculated with distance coefficient by every of library’s methods. The following work includes set of mentioned comparison results using combination of string mutations, and also for each transformation separately. Additionally, methods were compared by their performance. During tests, computational complexity of each method was estimated and also source code execution time was measured. To compare performance of methods, they were tested on ten times longer names. Due to the fact that solutions built in Python are relatively slow, attempt to improve library by implementing it in Cython and C++ was taken. Transformed methods were executed on the same database as Python library. Improvements of source code were compared by execution time and transformation cost. Library was made and tested in PyCharm Community IDE, whereas C++ implementation was written in Qt Creator.
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Eryk Kołodziejczyk (FM) Eryk Kołodziejczyk,, Faculty of Mechatronics (FM)
Title in Polish
Przybliżone porównanie nazw kontrahentów z wykorzystaniem języka Python
Supervisor
Anna Sztyber (FM/IACR) Anna Sztyber,, The Institute of Automatic Control and Robotics (FM/IACR)Faculty of Mechatronics (FM)
Certifying unit
Faculty of Mechatronics (FM)
Affiliation unit
The Institute of Automatic Control and Robotics (FM/IACR)
Study subject / specialization
, Automatyka i Robotyka (Automation and Robotics)
Language
(pl) Polish
Status
Finished
Defense Date
27-05-2019
Issue date (year)
2019
Reviewers
Piotr Duszak (FM/IACR) Piotr Duszak,, The Institute of Automatic Control and Robotics (FM/IACR)Faculty of Mechatronics (FM) Anna Sztyber (FM/IACR) Anna Sztyber,, The Institute of Automatic Control and Robotics (FM/IACR)Faculty of Mechatronics (FM)
Keywords in Polish
Przybliżone porównywanie napisów, przetwarzanie języka, Python, Cython, C++
Keywords in English
Approximated string matching, natural language processing, Python, Cython, C++
Abstract in Polish
W sporządzonej pracy podjęto się napisania biblioteki metod przybliżonego porównywania napisów. Biblioteka została napisana w wysokopoziomowym języku programowania Python. Podjęty problem porównywania napisów jest jednym z wyzwań współczesnej informatyki, a zagadnienie to dotyczy zarówno tekstu pisanego jak i mówionego, w przypadku przetwarzania mowy. Porównywanie napisów to zadanie podejmowane zarówno w pracach naukowych, na przykład przy porównywaniu sekwencji DNA, jak i w biznesowych projektach, tak jak omawiane w niniejszej pracy porównywanie nazw kontrahentów. Opracowane rozwiązanie porównuje parę napisów poprzez obliczenie współczynnika odległości. W przypadku kiedy napisy są identyczne, współczynnik wynosi 1, zaś kiedy są kompletnie inne, wynosi 0. W bibliotece zestawiono metody Hamminga, Levenshteina, Jaro, Jaro – Winklera oraz Ratcliffa – Obershelpa. Metody różnią się między sobą budową, sposobem liczenia współczynnika dystansu oraz wydajnością. Napisaną bibliotekę przetestowano na bazie kontrahentów, którą poddano różnym zniekształceniom. Wzorcową listę porównano z uszkodzoną, każda z par napisów została poddana obliczeniu współczynnika dystansu przez wszystkie zawarte w bibliotece metody. Niniejsza praca zawiera zestawienie wyników tych porównań przy zastosowaniu wszystkich przekształceń napisów, oraz dla każdego zniekształcenia oddzielnie. Metody porównano również pod kątem ich wydajności, oszacowano ich złożoność obliczeniową i zmierzono czasy wykonania każdej z nich. Porównano także działanie biblioteki dla 10 – krotnie dłuższych napisów. Z racji tego, iż rozwiązania budowane w Python są stosunkowo wolne, przeprowadzono próbę ulepszenia biblioteki poprzez zaimplementowanie jej w Cython oraz C++. Tak przekształcone metody wykonano na tej samej bazie co w przypadku Python. Porównano czasy ich wyegzekwowania, oraz koszty przekształcenia biblioteki Python do Cython oraz C++. Bibliotekę sporządzono i testowano za pomocą środowiska PyCharm Community, zaś jej implementację w C++ napisano w programie Qt Creator.
File
  • File: 1
    Praca_inżynierska_278211_Eryk_Kołodziejczyk_v2.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 33976

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT314a5aedea1b424d8235b401321aa4d8/
URN
urn:pw-repo:WUT314a5aedea1b424d8235b401321aa4d8

Confirmation
Are you sure?
Report incorrect data on this page