)
Cilvēku ikdienā arvien lielāku nozīmi ieņem informācija un tās pieejamība. Bieži ir nepieciešams ātri atrast vajadzīgo informāciju vai arī salīdzināt dažādus informācijas avotus. Protams, ka lielākā daļa no tās ir pieejama digitāli. Šī informācija ir binārā koda izskatā, ko 1689.gadā izgudroja Gotfrīds Leibnics [1]. Interesanti, ka binārā koda lielākais pielietojums ir tieši IT, kas parādījās tikai pēc gandrīz trīs gadsimtiem. Katrs no mums, kurš ikdienā izmanto e-pastu, īsziņas, “whatsapp” lietotni vai kādu citu saziņas rīku, saskarās ar bināro kodu. Jebkuru aizsūtīto informāciju dators vispirms pārvērš binārajā kodā, parasti ar koda palīdzību [2], tad to aizšifrē. Aizšifrēto bināro virkni ar interneta palīdzību nosūta adresātam, to atšifrē un tad atkal ar ASCII koda palīdzību atgriež oriģinālo tekstu un tas nonāk saņēmēja e-pastā. Tas viss, protams, notiek sekunžu laikā.
Ir atsevišķa matemātikas nozare “Vārdu kombinatorika”, kas fokusējas uz vārdu un formālo valodu izpētes [3], [4]. Pārsvarā par alfabētu izmanto kopu, kas sastāv tikai no nulles un vieninieka (binārs alfabēts). Un tad šīs kopas elementus var kārtot vienu aiz otra (matemātiski to sauc par konkatenāciju), radot virknes, ko vārdu kombinatorikā sauc par vārdiem. Piemēram, arī uz latviešu valodu var skatīties no vārdu kombinatorikas viedokļa – šajā gadījumā alfabēts sastāvētu no visiem burtiem, atstarpes, interpunkcijas zīmēm. Un liekot pareizā secībā tos vienu pie otra tiek iegūts latviešu valodas tekstu.
Laikā no 2021.gada 1. janvāra līdz 2023.gada 30.jūnijam šī raksta autors veica ES struktūrfonda projektu “Nestriktas pseidometrikas pielietojumi vārdu kombinatorikā” (Nr. 1.1.1.2/VIAA/4/20/706). Sīkāku un detalizētāku informāciju par šo projektu varat aplūkot projekta mājas lapā - latviešu valodā vai angļu valodā. Šī raksta ietvaros populārzinātniskā veidā tiks pastāstīts, kāds bija projekta mērķis, uzdevumi un rezultāti.
Šī projekta mērķis bija izveidot pavisam jaunu nestriktu metriku [5], kas palīdzētu aprakstīt attālumu starp jebkurām divām galīgām vai bezgalīgām binārām virknēm daudz objektīvāk nekā zinātniskajā literatūrā līdz šim aprakstītas. Projekta galvenie uzdevumi bija divi – nestriktās metrikas izpēte un jaunas nestriktas metrikas konstruēšana un attīstīšana, lai salīdzinātu bināras virknes. Zinātniskajā literatūrā ir vairākas parastās metrikas [6], [7], [8], [9], kas definē attālumu starp divām bezgalīgām binārām virknēm, bet neviena no tām nav piemērota un nedod rezultātu, kas tiešām aprakstītu subjektīvos un intuitīvos attālumus.
Rezultāts, ko izdod metrika (tā ir funkcija, kas tika apgūta pamatskolā un vidusskolā), interpretē attālumu. Jo mazāks rezultāts, jo pieņem, ka attiecīgie objekti viens otram ir tuvāki (tie ir vienādāki). Jo lielāks rezultāts, jo attiecīgie objekti viens otram ir tālāki (tie vairāk atšķiras). Ja rezultāts ir 0, tad objekti ir vienādi, bet ja rezultāts ir liels (atkarībā no definētās metrikas lielākā vērtība var būt gan 1, gan 2, gan bezgalība, gan jebkura cita vērtība), tad objekti ļoti atšķiras. Pavisam vienkāršs pretpiemērs ir sekojošs. Pieņemsim, ka x ir bezgalīgs binārs vārds, kas satur visus vieniniekus, y ir bezgalīgs vārds, kam pirmajā pozīcijā ir nulle, bet pārējie vieninieki, bet z ir bezgalīgs vārds, kas satur visus nulles. Tātad x=(1,1,1,1,1,1,1,…), y=(0,1,1,1,1,1,1,…) un z=(0,0,0,0,0,0,…). Varam uzdod sekojošu jautājumu – kas ir tuvāki/vienādāki viens ar otru, x ar y vai x ar z? Autors ir pārliecināts, ka vairums atbildēja, ka x ar y ir tuvāki viens otram, jo atšķiras tikai vienā pozīcijā, bet x ar z ir pilnīgi atšķirīgi, tātad atrodas viens no otra ļoti tālu.
Viena no literatūrā līdz šim zināmajām parastām metrikām dod rezultātu, ka abi pāri atrodas viens no otra vienādā attālumā. Tam par pamatojumu metrikai tam ir tas, ka tā kā pirmā pozīcija nesakrīt ne pirmajam pārim, ne otrajam pārim, tad abi pāri ir pilnīgi atšķirīgi. Bet subjektīvi tiek saprasts, ka nav patiesība.
Zinātniskajā literatūrā ir definēta arī cita metrika, kas secina, ka pirmais pāris ir daudz tuvāki viens otram nekā otrais pāris. Bet arī šai metrikai var atrast citu, pavisam triviālu piemēru, kas dod rezultātu, kāds subjektīvi netiek sagaidīts. Pieņemsim, ka ir trīs bezgalīgi vārdi x=(0,0,0,0,0,0,…), y=(1,0,0,0,0,0,…) un z=(0,1,1,1,1,1…). Atkal var uzdot jautājumu - kas ir tuvāki/vienādāki viens ar otru, x ar y vai x ar z? Iespējams arī šeit vairums atbildētu, ka tuvāki viens otram ir x ar y, jo tie atšķiras tikai ar vienu simbolu. Savukārt x ar z sakrīt tikai vienā pozīcijā, bet visās pārējās atšķiras.
Augstākminēto piemēru dēļ arī tika izstrādāts šis projekts ar šādu mērķi un uzdevumiem. Jau pirms šī projekta bija mēģinājumi uzkonstruēt vairāku veidu nestriktās metrikas, kas salīdzina divas bezgalīgas binārā koda simbolu virknes, bet tās nepalīdzēja atrisināt problēmu ar augstāk minētiem pretpiemēriem [10], [11]. Projekta sākumā, balstoties jau uz iepriekšējo rakstu konstrukcijām un modificējot klasisko nestriktās metrikas definīciju, tika ieviesta jauna definīcija – nestrikta aproksimējoša metrika. Šīs metrikas rezultējošās vērtības ir skaitļu intervāls no vienas trešdaļas līdz viens, kur viens nozīmē, ka bezgalīgie vārdi ir pilnīgi vienādi, bet viena trešdaļa nozīmē, ka tie ir pilnīgi atšķirīgi. Ar tās palīdzību izdevās novērst nepilnības arī otrajā pretpiemērā [12], kas deva rezultātu, ka x ar y ir gandrīz vienādi, bet x ar z ir gandrīz pilnīgi pretēji.
Otrā metode [13], kas tika izveidota šī projekta ietvaros, bija no matemātiskā viedokļa ar pavisam citu ideju. Šī raksta ietvaros izdevās ne tikai vēlreiz atrisināt pretpiemēru problēmu, bet šo problēmu vispārināt un dot dažāda veida skaitliskos rezultātus. Abām metodēm nestriktās metrikas definēšanā tika īstenota parametra [14] ieviešana. Abām metodēm parametra lielums nosaka to, cik liela nozīme rezultējošā vērtībā būs simbolu sakrišanai vai nesakrišanai atkarībā no tā, kurā pozīcijā mēs salīdzinām. Abās metodēs ir spēkā sakarība, ka jo lielāks parametrs, jo mazāks svars [15] binārā koda virknes simboliem.
Tāpat projekta ietvaros tika izveidota programma, kas ļauj ikvienam lietotājam salīdzināt attālumu galīgām bināra koda virknēm ar abām projekta laikā izstrādātajām metodēm (jo bezgalīgi garas virknes ir neiespējami ievadīt programmā). Ikvienam šī raksta lasītājam ir iespējams pārbaudīt, kuras no attiecīgajām lietotāja ievadītajām simbolu virknēm ir tuvākas vai tālākas). Pie tam lietotājam ir iespēja izmainīt katras metodes parametru, kas maina svaru binārā koda virknes simboliem.
Atsauces:
2. ASCII table
3. Combinatorics on words, Wikipedia
4. Lothaire, M. Algebraic Combinatorics On Words (2001).
6. Xia, ZQ., Guo, FF. Fuzzy metric spaces. JAMC 16, 371–381 (2004). 10.1007/BF02936175
7. Allouche, J.-P.; Shallit, J. Automatic Sequences: Theory, Applications, Generalizations; Cambridge University Press: Cambridge, UK, 2003.:
8. Apostol, T.M. Introduction to Analytic Number Theory; Springer: New York, NY, USA, 1986.
9. Calude, C.S.; Jurgensen, H.; Staiger, L. Topology on words. Theor. Comput. Sci. 2009, 410, 2323–2335.
10. Bets, Raivis and Alexander P. Sostak. “Fragmentary Fuzzy Pseudometrics: Basics of the Theory and Applications in Combinatorics on Words.” Balt. J. Mod. Comput. 4 (2016)
11. Šostak, A., Bēts, R. (2018). Fuzzy φφ pseudometrics and Fuzzy φφ-pseudometric Spaces. In: Kacprzyk, J., Szmidt, E., Zadrożny, S., Atanassov, K., Krawczak, M. (eds) Advances in Fuzzy Logic and Technology 2017. EUSFLAT IWIFSGN 2017 2017. Advances in Intelligent Systems and Computing, vol 643. Springer, Cham. 10.1007/978-3-319-66827-7_30
12. Bēts, R., Šostak, A. “Some remarks on strong fuzzy metrics and strong fuzzy approximating metrics with applications in word combinatorics”, MATHEMATICS 10 (2022) art. 738.
13. Bēts, R., Šostak, A., Miķelsons, E.M. (2022). Parameterized Metrics and Their Applications in Word Combinatorics. In:,et al. Information Processing and Management of Uncertainty in Knowledge-Based Systems. IPMU 2022. Communications in Computer and Information Science, vol 1601. Springer, Cham. 10.1007/978-3-031-08971-8_23
Balsis: 1, vidējais vērtējums: 5