-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy paththesis.tex
executable file
·2880 lines (2384 loc) · 161 KB
/
thesis.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
\documentclass[FM,DP]{tulthesis}
% fonts, langs, packages...
\usepackage{polyglossia}
\setdefaultlanguage{czech}
\usepackage{fontspec}
\usepackage{xunicode}
\usepackage{xltxtra}
\setsansfont[Mapping=tex-text,BoldFont={* Bold},Numbers=OldStyle]{Myriad Pro}
\usepackage{hyperref}
\hypersetup{colorlinks=true, linkcolor=tul, urlcolor=tul, citecolor=tul}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{booktabs}
\usepackage{listings}
\usepackage[toc,page]{appendix}
\usepackage{amsmath}
\usepackage{amssymb}
\newcommand{\argument}[1]{{\ttfamily\color{\tulcolor}#1}}
\newcommand{\prikaz}[1]{\argument{\textbackslash #1}}
\newenvironment{myquote}{\begin{list}{}{\setlength\leftmargin\parindent}\item[]}{\end{list}}
\sloppy
\usepackage{array}
\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}m{#1}}
% syntax highlighting
\usepackage[newfloat]{minted}
\usepackage[labelfont=bf,font=it]{caption}
\usepackage{etoolbox}
\definecolor{bg}{rgb}{0.95,0.95,0.95}
\setminted{bgcolor=bg, frame=single, rulecolor=\color{bg}, breaklines=true}
\makeatletter
\patchcmd{\minted@colorbg}{\noindent}{\medskip\noindent}{}{}
\apptocmd{\endminted@colorbg}{\par\medskip}{}{}
\makeatother
\newenvironment{code}
{\filbreak\captionsetup{type=listing}}{\filbreak}
\SetupFloatingEnvironment{listing}{name=Výpis}
\renewcommand{\floatpagefraction}{.8}%
% brak lines in \url{}
\makeatletter
\g@addto@macro{\UrlBreaks}{\UrlOrds}
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\TULtitle{Vyhledávání jako služba}{Search as a Service}
\TULprogramme{Aplikovaná informatika}{Applied Informatics}
\TULbranch{Informační systémy a technologie}{Information Technologies}
\TULauthor{Bc. Luděk Veselý}
\TULsupervisor{Prof. Ing. Zdeněk Molnár, CSc.}
\TULreader{Ing. Ivan Jelínek}
\TULyear{2017}
\renewcommand{\listlistingname}{Seznam výpisů programů}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\pagenumbering{gobble}
\ThesisStart{male}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{acknowledgement}
Rád bych poděkoval Prof. Ing. Zdeňkovi Molnárovi, CSc. za vedení mé diplomové práce
a veškerou pomoc při jejím řešení.
\end{acknowledgement}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstractCZ}
Tato diplomová práce se zabývá návrhem a tvorbou plnotextového vyhledávání, které je poskytováno jako služba,
přičemž samotné vyhledávání se zaměřuje na~použití v~elektronických obchodech. V~úvodu práce je analyzována
problematika elektronického obchodování, jsou vysvětleny související pojmy a definovány požadavky na~samotné
vyhledávání. Následně jsou popsány teoretické možnosti textového vyhledávání pro~dané použití. Na~základě
analýzy je vytvořen návrh aplikace, který je následně implementován v~programovacím jazyce Go s~využitím
nástroje Elasticsearch. V závěru práce je aplikace testována, čímž je ověřeno splnění požadavků na~vyhledávání
z~pohledu kvality vyhledávání, rychlosti i uživatelské přívětivosti služby.
\end{abstractCZ}
\vspace{1cm}
\begin{klicovaslovaCZ}
Plnotextové vyhledávání, software jako služba, elektronický obchod, Elasticsearch
\end{klicovaslovaCZ}
\vspace{2cm}
\begin{abstractEN}
This thesis is focused on design and implementation of fulltext searching, which is provided as a servise.
The searching itself is focused on the utilization in e-shops. At the beginning, the question of e-commerce
is analysed, the related terms are explained and the requirements of searching are identified. Then, the
theoretical ways of text searching in this context are described. On the analyse is created a conception
of application, which is further implemented in the language Go with the usage of Elasticresearch.
Finally, the application is tested, which should examine not only the quality and speed of searching
but also the user-friendliness.
\end{abstractEN}
\vspace{1cm}
\begin{klicovaslovaEN}
Full text search, Software as a service, E-shop, Elasticsearch
\end{klicovaslovaEN}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagenumbering{roman}
\setcounter{page}{2}
\addcontentsline{toc}{chapter}{Obsah}
\tableofcontents
\clearpage
% obrazky
\addcontentsline{toc}{chapter}{Seznam obrázků}
\listoffigures
\clearpage
% tabulky
\addcontentsline{toc}{chapter}{Seznam tabulek}
\listoftables
\clearpage
% vypisy programu
\addcontentsline{toc}{chapter}{Seznam výpisů programů}
\listoflistings
\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagenumbering{arabic}
\chapter{Úvod}
Vyhledávání je jednou z klíčových funkcí elektronického obchodu. Umožňuje rychlé nalezení
hledaného produktu, což přináší zákazníkům úsporu času a usnadňuje tak orientaci na webu.
Textové vyhledávání však není snadné implementovat, protože je třeba si poradit se zpracováním
přirozeného jazyka a dalšími problémy -- je totiž vhodné mít určitou úroveň znalosti principů samotného
vyhledávání včetně souvisejících oborů a technologií. Implementace kvalitního vyhledávání
tak může být pro provozovatele elektronického obchodu náročná jak časově, tak finančně.
Tento nástroj je poskytován jako služba se všemi výhodami i omezeními s tímto principem spojenými.
Měl by provozovatelům elektronických obchodů usnadnit implementaci vyhledávání, zároveň
by měl poskytovat tak kvalitní výsledky vyhledávání, aby neměl provozovatel obchodu potřebu
přecházet k jiným nástrojům. Konkrétní cíle diplomové práce jsou popsány v následujících odstavcích.
\section{Cíle práce}
Cílem této práce je \textbf{navrhnout a vytvořit nástroj, který je nabízen jako služba a umožňuje
provozovatelům elektronických obchodů snadnou implementaci plnotextového vyhledávání do elektronického
obchodu.} K~dosažení tohoto cíle je třeba naplnit cíle dílčí.
Prvním takovým cílem je provedení analýzy problému a to jak z~pohledu obchodního, tak
z~pohledu samotné problematiky vyhledávání. Co se týče prvního pohledu, je třeba
analyzovat potřeby zákazníků, zjistit, jaká jsou specifika oblasti elektronického obchodování
a definovat kritéria, jejichž naplnění je pro provozovatele elektronických obchodů klíčové.
Z~pohledu problematiky vyhledávání je třeba provést analýzu této disciplíny a utřídit
tak znalosti potřebné k poskytnutí kvalitních výsledků plnotextového vyhledávání.
Dalším dílčím cílem je vytvořit návrh řešení problému jednak na základě znalosti potřeb
zákazníků a také na základě znalosti problematiky plnotextového vyhledávání. Tento návrh musí
být v~dalším kroku implementovatelný.
Předposledním dílčím cílem je samotná implementace aplikace dle jejího návrhu. Obnáší to výběr
vhodných nástrojů, jejich nasazení do produkčního prostředí, naprogramování jednotlivých
služeb a konečně také ověření samotné implementace. Tu je třeba porovnat se stanovenými požadavky
a ověřit tak jejich naplnění. Tento krok potvrdí nebo vyvrátí spránvost implementace.
\section{Cílová skupina}
Cílovou skupinou je chápán ten, komu je určen samotný text této práce, nejde tedy
o~uživatele vzniklé aplikace.
První cílovou skupinou je vývojář, řešící problém plnotextového vyhledávání produktů
při implementaci elektronického obchodu. Takovému čtenáři by měla práce poskytnout dostatečné
teoretické znalosti potřebné pro implementaci vyhledávání. Užitečná také může být konkrétní
implementace, která je v této práci popisována.
Další možnou cílovou skupinou je provozovatel elektronického obchodu, který přemýšlí,
jakým způsobem zlepšit (případně zavést) plnotextové vyhledávání. V~této práci získá
přehled o~složitosti samotné implementace, poskytne mu komentovaný soupis možných řešení
a konečně také poskytne funkční službu, kterou může okamžitě na~webový portál napojit.
Poslední cílovou skupinou budiž kdokoli, kdo se zajímá o problematiku plnotextového
vyhledávání v českém jazyce. V této práci nalezne soupis problémů souvisejicích s češtinou,
které je třeba řešit. Dále zde nalezne konkrétní implementaci, kterou se může inspirovat
při řešení obdobného problému.
\section{Použité metody}
V~této části jsou popsány metody použité k~naplnění jednotlivých cílů. Pro zkoumání problému
oboru je provedena analýzu trhu, nabízí se také možnost dotazování potenciálních uživatelů,
případně je možné vyjít ze zkušeností autora. Pro porozumění problematice vyhledávání
je provedena rešerše literatury. Vzhledem k množství dostupné literatury bude třeba provést
syntézu těchto informací. Při vytváření návrhu řešení bude použito modelování, výstupem
by tedy měl být model řešení.
\section{Struktura práce}
V první části práce popisuji problematiku vyhledávání v~prostředí elektronického obchodování.
Definuji zde jednak kontext, v~kterém se pohybuji a dále také popisuji problémy,
které v~tomto prostředí existují. Snažím se identifikovat potencionálního uživatele
a definovat jeho požadavky na~plnotextové vyhledávání. Toto prostředí má svá specifika,
která také popisuji a vysvětluji, proč jsem se na tuto oblast zaměřil. V~závěru této části porovnávám
existující nástroje umožňující implementaci vyhledávání a zjišťuji tak, proč má smysl
vytvářet další službu, jaká je její přidaná hodnota.
V druhé části se zabývám teorií plnotextového vyhledávání. Popisuji zde celý
proces od analýzy vstupních dat, přes jejich indexaci, až po samotné vyhledávání.
Tyto poznatky budou následně využity k~naplnění požadavků na vyhledávání, k~zajištění
kvalitních výsledků vyhledávání.
V další části práce navrhuji samotnou aplikaci tak, aby vyhovovala požadavkům a zároveň byla
následně implementovatelná. Porovnávám zde dostupné nástroje, definuji případy užití aplikace
a vytvářím model výsledné aplikace.
Poté popisuji konkrétní implementaci v~jazyce Go s~pomocí úložiště
Elasticsearch. Výstupem této části je otestovaný spustitelný program, který umožňuje provádět
indexaci produktů a jejich následné vyhledávání. Tento program je nasazen do produkčního
prostředí a při každé změně zdrojových kódů je aplikace aktualizována.
V poslední části práce je provedeno ověření funkčnosti aplikace, zejména vůči požadavkům na její funkčnost.
Je testována kvalita vyhledávání vzhledem k zpracování přirozeného jazyka, rychlost aplikace
při zátěži a také uživatelská přívětivost, tedy snadnost napojení služby na elektronický obchod.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Komentovaná rešerše použitých informačních zdrojů}
V této kapitole popisuji jednak práce, které již na VŠE vznikly, avšak od této práce se odlišují.
Dále komentuji literaturu, ze které je nejvíce čerpáno a je tak stěžejním zdrojem informací pro vznik
této práce.
\section{Existující práce obdobného tématu}
Na VŠE již vzniklo několik prací, zabývající se textovým vyhledáváním. Mezi nejpropracovanější
patří \textbf{Návrh vyhledávacího systému pro moderní potřeby} od Bc. Tomáše Maršálka, která
se zabývá implementací vyhledávání, které si dokáže poradit s nepřesným nebo neúplným zadáním
hledaného výrazu. Výstupem této práce je program, který je možné pro takové vyhledávání použít.
Další prací zabývající se textovým vyhledáváním je \textbf{Pragmatický lematizátor českých slov} od
Bc. Matěje Vacka. Přestože práce vychází z podobného teoretického základu, jejím výstupem je
opět pouze nástroj pro použití při implementaci vyhledávání. Tato práce se odlišuje v~tom,
že spíše než vytvoření jednoúčelového nástroje si dává za cíl vytvořit prakticky použitelný
nástroj, který však dílčí části (například zpracování přirozeného jazyka) využívá jako
prostředek k poskytnutí komplexní služby.
\section{Použitá literatura}
Při tvorbě této práce vycházím z literatury uvedené v závěru práce. Teoretické znalosti však
nejvíce čerpám z knihy \textbf{Počítačové zpracování přirozeného jazyka}~\cite{strossa}
od Petra Strossy, přičemž nejužitečnější pro tuto práci je hned první kapitola
zabývající se automatizovaným indexováním textů. Knih zabývající se textovým vyhledáváním existuje
celá řada -- dále čerpám především z knih \textbf{Searching in the 21st Century}~\cite{searching}
a \textbf{Mining Text Data}~\cite{mining}.
Dále je třeba mít povědomí o oblasti elektronického obchodování, což je přehledně shrnuto v~knize
\textbf{E-commerce} Petra Suchánka~\cite{e-commerce}. Z této knihy je pro práci nejpřínosnější
její první polovina, která pojednává jak o obecných termínech, tak je důkladně vysvětluje.
Při návrhu API je třeba mít povědomí o tom jak jej navrhnout i jak jej v konkrétním programovacím
jazyce implementovat. Obecně o návrhu API pojednává kniha \textbf{Build APIs You Won't Hate} \cite{api},
která je průvodcem návrhu dobře použitelného api od samého počátku, včetně ukázky na konkrétních příkladech.
Pro seznámení s jazykem Go na komplexní úrovni je dostatek informací v knize~\textbf{Go in Action}
\cite{go-in-action}, která je další z řady knih nakladatelství Manning Publications pojednávající
o řadě dalších nástrojíů. Vzhledem k specifickému užití jazyka jsem čerpal z dalších dvou knih
o tomto programovacím jazyce -- \textbf{Mastering Concurrency in Go} \cite{go-concurrency} a
\textbf{Build web applications with Golang} \cite{go-xml}. Co se samotného nasazování aplikace týče,
velmi přínosná je kniha \textbf{The DevOps 2.0 Toolkit} \cite{devops}, která by se dala chápat jako průvodce
světem DevOps. Přináší spoustu informací pro pochopení tohoto přístupu, což je doloženo řadou
příkladů. Specielně pro důkladnější porozumění nástroji Docker je k dispozici kniha
\textbf{Docker: Up \& Running} \cite{docker}, která s tímto nástrojem čtenáře seznámí víc než důkladně.
Vzhledem k použití nástroje Elasticsearch je třeba mít dostatek informací také o tomto nástroji.
Jedna z nejpodrobnějších knih je \textbf{Elasticsearch: The Definitive Guide}, která
popisuje veškerou funkčnost tohoto nástroje a popis doplňuje o teoretické informace nutné
k pochopení dané problematiky. Elasticsearch se však velmi rychle vyvíjí a tak tato kniha
nereflektuje přesně aktuální stav. Konkrétní funkčnost je tedy třeba vždy ověřovat vůči
aktuální dokumentaci \textbf{Elasticsearch Reference}~\cite{elastic-reference}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Analýza byznys požadavků na aplikaci}
První část diplomové práce popisuje problematiku plnotextového vyhledávání
v~prostředí elektronických obchodů. Nejprve je čtenář uveden do problematiky elektronického
obchodování a obeznámen s základními pojmy a principy. Následně je popsán problém,
který je řešen, a jsou definovány konkrétní podmínky, za kterých bude výsledný nástroj
přínosný a použitelný. Jsou zde také diskutovány stávající možnosti implementace
plnotextového vyhledávání, porovnány alternativní služby a zdůvodněno vytváření nového nástroje.
\section{Vysvětlení základních pojmů}
Pro usnadnění orientace v této práci jsou nejprve vysvětleny dále používané pojmy. Jedná se
vesměs o známé termíny, přesto je důležité uvést jejich význam na pravou míru.
\subsection*{Elektronické obchodování}
Termín elektronické obchodování (e-commerce) označuje veškerou činnost spojenou s obchodováním
realizovaným prostřednictvím sítě internet \cite[strana~11]{e-commerce}. Spadá sem distribuce, nákup,
prodej, marketing, servis produktů. Elektronické obchodování se dále podle dělí dle zaměření na cílové
skupiny, z nichž nejpodstatnější jsou B2C (zaměřeno na koncové zákazníky) a B2B (zaměřeno na obchodníky)
\cite[strana~17]{e-commerce}. Elektronické obchodování je podmnožinou
elektronického podnikání (e-business), které oznažuje veškeré obchodní a výrobní aktivity,
zatímco elektronické obchodování se týká samotného prodeje zboží a služeb.
\subsection*{Elektronický obchod}
Elektronický či internetový obchod (e-shop) je webová aplikace, jejímž prostřednictvím
provozovatel obchodu prodává zboží nebo služby zákazníkům \cite[strana~16]{e-commerce}.
Jedná se o podmožinu elektronického obchodování, jde tedy o jeden z možných prodejních
kanálů v prostředí internetu. Elektronický obchod je specifickou webovou aplikací, v~níž
se opakují určité vzorce. Konkrétně je to katalog produktů, kategorizace zboží,
vkládání položek do košíku, platba objednávky, možnost kontaktu s~zákaznickou podporou
prostřednictvím on-line chatu přímo v aplikaci.
V elektronickém obchodě lze shledávat řadu podobností s obchodem kamenným, který zákazníci
navštěvují osobně. Některé vlastnosti elektronického obchodu jsou zřejmě inspirovány
obchody kamennými (procházení zboží podle kategorií, přidávání položek do košíku,
uplatnění slevových poukázek při platbě). Často však elektronický obchod využívá možností,
které webové prostředí nabízí (filtrace a řazení položek podle parametrů, vrácení se
k naplněnému košíku, porovnávání zboží napříč obchody).
\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{e-commerce.pdf}
\caption[Vztah elektronického podnikání, obchodování a podnikání]{Vztah elektronického podnikání, obchodování a podnikání (Zdroj: \cite{strossa})}
\label{e-commerce}
\end{figure}
Zcela zásadní výhodou elektronického obchodu oproti návštěvě obchodu kamenného
je možnost vytvoření objednávky z pohodlí domova a její následné doručení zásilkovou
službou. Tento přístup především šetří čas strávený cestou do obchodu a čas strávený
v~obchodě. Například v segmentu nákupu potravin může být výhodou to, že je takový
nákup hygieničtější a zboží bude doručeno v lepším stavu díky uzpůsobeným vozům dopravců.
Výhody ale vznikají i pro provozovatele -- nemusí zřizovat prodejnu včetně jejího vybavení a
zaměstnance, mohou efektivněji navrhnout sklad, nebo dokonce využít automatizace
při kompletaci objednaného zboží.
\subsection*{Plnotextové vyhledávání}
Plnotextové vyhledávání (full-text search) je způsob vyhledávání v textových datech,
kdy se vyhledává uživatelem formulovaný dotaz v invertovaném souboru (někdy také
indexovém souboru nebo invertovaném indexu), tedy v souboru obsahující výrazy,
podle nichž je daný záznam jednoduše vyhledatelný \cite[strana~15]{strossa}.
Proces, kterým vzniká indexový soubor, se nazývá indexace. Tato problematika je podrobněji
popisována v kapitole \ref{ch:indexace}.
\section{Vysvětlení problému, který je řešen}
Plnotextové vyhledávání je rychlým prostředkem nalezení konkrétního produktu
v elektronickém obchodě. Typicky je využito zákazníky, kteří jsou na webu
s konkrétní potřebou a jsou schopni formulovat výraz, podle kterého produkt
hledají. Může jít o název tybu produktu, jeho značku, variantu nebo kategorii.
Pro takového uživatele je procházení webu procházením kategorií zdlouhavé
a právě plnotextové vyhledávání mu může zásadně zrychlit cestu k nalezení
hledaného produktu.
Důležitost plnotextového vyhledávání navíc roste s rostoucím počtem produktů a kategorií,
v kterých je složité se orientovat. Uživatel tak může vyhledávání využít už pro
nalezení kategorie, která se nachází v dlouhém a nepřehledném menu.
\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{atoto-vyhledavani.png}
\caption[Ukázka plnotextového vyhledávání]{Ukázka plnotextového vyhledávání v elektronickém obchodu atoto.cz}
\label{atoto-vyhledavani}
\end{figure}
Implementace plnotextového vyhledávání však není triviální záležitostí. Vstup uživatele
je v přirozeném jazyce, takže je třeba jej odpovídajícím způsobem zpracovat,
aby bylo vůbec vyhledávání na webu použitelné. Studium této problematiky
může být zdlouhavé a v konečném důsledku drahé. Je třeba brát v potaz
i případnou složitost dalších nástrojů, které bude třeba pro funkční vyhledávání spravovat,
to s sebou nese více prostoru k potenciálním chybám.
Pokud bude k dispozici hotové řešení, které bude snadno nasaditelné na elektronický obchod
a bude umožňovat jednoduché uzpůsobení potřebám konkrétního webu, bude to výrazná úspora jak
času, tak peněz provozovatele elektronického obchodu.
Veškeré výše jmenované problémy mohou být značnou bariérou pro implementaci kvalitního vyhledávání,
přes kterou se tak množství zejména menších obchodů nepřenese. Problémy lze shrnout do následujících bodů:
\begin{itemize}
\item Provozovatel elektronického obchodu chce nasadit textové vyhledávání na web, to se musí naprogramovat
\item Aktuální podoba textového vyhledávání na webu je nekvalitní
\item Vyhledávání na webu je pomalé, s přibývajícími produkty stále hůře použitelné
\end{itemize}
Řešení vyhledávání svépomocí je navíc z teoretického hlediska obtížné z~těchto důvodů:
\begin{itemize}
\item Je nutná znalost principů přirozeného jazyka
\item Je nutná znalost nástrojů, které umožňují pokročilou práci s jazykem
\item Je nutná znalost technologií, které poskytnou vyhledávání dostatečně rychlé
\end{itemize}
\section{Specifika elektronického obchodování}
V prostředí elektronického obchodování existují jisté vzorce, které se opakují a odlišují
toto prostředí od ostatních. Vyhledávají se zpravidla produkty (případně služby), které jsou
zařazeny do určitých kategorií a disponují atributy jako cena, název, kód, popis, url, obrázek,
dostupnost a dalšími parametry, které bývají číselné (hmotnost, objem) nebo výčtové (barva, značka).
Z toho vyplývá co a podle čeho se bude vyhledávat. Produkty mívají jednoznačné identifikátory,
které jsou navíc standardizovány (EAN, ISBN). Pomocí těchto kódů je možné vyhledat produkty
napříč elektronickými obchody nebo je párovat v cenových srovnávačích. Pro vyhledávání
je však nejdůležitější název produktu, případně jeho varianta, která upřesňuje konkrétní
verzi produktu. Méně častěji je nutné vyhledávat v popisu produktu, kde bývá uveden
jak slovní popis, tak výpis parametrů.
U produktů dále bývá evidována cena, která může být interně uložena v kombinaci s marží.
Obchody operující se zlevněným zbožím pak mívají uvedenou cenu jak před slevou, tak po této
slevě, aby zákazník viděl, kolikaprocentní sleva je na produktu. I samotná cena produktu
(případně marže prodejce) může hrát svou roli ve vyhledávání.
\section{Definice požadavků na vyhledávání} \label{ch:pozadavky-vyhledavani}
Požadavky na samotné vyhledávání jsou ovlivněny prostředím, ve kterém vyhledávání
probíhá a uživateli, kteří vyhledávání využívají. Primárně by mělo být možné
nalézt daný produkt podle jeho názvu, nebo části názvu, případně podle kódu produktu,
pokud je k~dispozici. Produkt by měl být ale vyhledatelný i podle dalších atributů,
jako je název kategorie nebo název značky výrobce. Někdy dokonce uživatel nemusí
vyhledávat konkrétní produkt, ale jen produkty dané značky nebo kategorie, což by
měl systém také umět rozpoznat.
Podoba vyhledávaných výrazů bude zadávána zákazníky v přirozeném jazyce, s čímž by si mělo
vyhledávání také poradit. Konkrétně jde o tvarosloví, kdy může uživatel zadat výraz
například v jiném pádu, než je uvedeno v názvu produktu. Dále jde o vyrovnání se
s~chybami, které mohou vzniknout při formulaci vyhledávaného výrazu -- překlepy nebo
pravopisné chyby. V neposlední řadě jde také o vztah slova k jeho významu, kdy může
jedno slovo mít více významů (homonymum) nebo naopak více slov může odpovídat jednomu výrazu
(synonymum).
Další problematikou při zadávání hledaného výrazu uživatelem, je poskytování relevantních výsledků
už ve chvíli, kdy uživatel formuluje dotaz, tedy jej teprve píše. V takovém případě je třeba
odhadnout, který výraz chce napsat a tuto informaci využít při zobrazení odpovídajících
výsledků.
Ve chvíli, kdy systém zná produkty, které odpovídají hledanému výrazu by měl
výsledky poskytovat ve vhodném pořadí, měl by tedy pracovat s relevancí výsledků vzhledem
k~zadanému výrazu. Toto může být velmi obtížné, protože každý uživatel má zájem o jiné
produkty a tak pro něj mohou být pro jeden výraz relevantní jiné produkty, než pro někoho
jiného. Dále do tohoto pořadí mohou vstupovat požadavky provozovatele elektronického obchodu
v případě, kdy má specifické požadavky na zboží, které chce nabízet přednostně. Důvodů
pro takové chování může být více, může souviset s marží konkrétních produktů,
nebo s filozofií samotného obchodu. Tato problematika je však značně rozsáhlá a vydala by
na samostatnou práci, v tomto okamžiku je tedy nutné využít "objektivní" relevance,
tedy řadit produkty pouze dle jejich podobnosti vzhledem k hledanému výrazu.
\section{Technické požadavky na aplikaci}
Na aplikaci je kladeno několik technických požadavků. Nejedná se o funkční požadavky, nýbrž
o požadavky související s použitelností, výkonností, spolehlivostí a podporou. Naplnění těchto
požadavků zajistí následný bezproblémový chod aplikace a uspokojení potřeb zákazníka.
Prvním technickým požadavkem na aplikaci je její rychlost. Ta je důležitá pro spokojenost
koncového zákazníka, který provádí vyhledávání. Všechny části aplikace nejsou z hlediska rychlosti
tak kritické, jedná se primárně o samotné vyhledávání. Akceptovatelná rychlost uživatelského rozhraní
v tomto případě je 100 ms \cite{amazon-100ms}, v ideálním případě do 50 ms \cite{stackshare-algolia}.
Pro naplnění tohoto požadavku je třeba, aby byla rychlost odezvy API co nejnižší.
Rychlost by dále nemělo výrazně ovlivňovat množství současných požadavků.
Aplikace by měla být navržena tak, aby ji bylo možné snadno škálovat při zvyšující se zátěži.
Dalším požadavkem je formát samotného API. Bude třeba použít takový formát, který bude
co nejsnadněji implementovaný v používaných webových technologiích pokud možno bez instalace
jakýchkoli rozšíření. To je důležité pro rychlé nasazení aplikace do provozu a odbourání
možných vstupních bariér při rozhodování o využití nástroje. Pro načtení produktů
z elektronických obchodů by bylo ideální využít stávajících exportů pro jiné systémy,
kterými by obchody mohly implementovat. Pokud by nic takového neexistovalo, můsí být vytvoření
exportu produktů pro provozovatele elektronického obchodu co nejsnažší.
Posledním technickým požadavkem je dokukemantace samotného API. Dokumentace musí být
dobře pochopitelná, tedy psaná přehledně, ideálně s konkrétními ukázkami použití.
Výhodou je také možnost vyzkoušet si práci s API vůči testovacímu prostředí,
kde nehrozí riziko vzniku chyb na produkčních datech.
\section{Popis oborů, kterých se práce dotýká}
Samotné řešení problematiky vyhledávání je výrazně interdisciplinární obor. Je nutné
mít značné povědomí o získávání informací, počítačovém zpracování přirozeného jazyka,
což souvisí jak s počítačovou lingvistikou, tak úzce s teorií formálních jazyků a překladačů.
Existuje také vztah mezi lingvistikou a logikou, jakožto vědě o myšlení, která se odehrává
v kategoriích lidského jazyka. Podobný vztah lze nalézt také s umělou inteligencí,
vzhledem k tomu, že používání přirozeného jazyka je inteligentní činností.
Díky tomu, že probíhá ukládání dat, je důležitá znalost teorie datových modelů.
Vzhledem k množství ukládaných dat se také můžeme dotýkat oboru Big Data.
V neposlední řadě je třeba porozumnět potřebám potenciálních uživatelů, tedy mít
určitou znalost podnikání a obchodování.
\section{Stávající možnosti implementace vyhledávání}
Na trhu existuje několik služeb, které umožňují implementaci plnotextového vyhledávání.
Ty se však liší funkčností, obtížností implementace i cenou. Níže popisuji nejvýznamější
z nich zejména vzhledem k požadavkům na aplikaci.
\subsection{Využití relační databáze}
První možností, jak vyhledávání implementovat je využití stávající databáze,
kterou elektronický obchod disponuje. Ať už se jedná o open source (MySQL, Postgres)
nebo komerční (SQL Server, Oracle) databázi, možnosti plnotextového vyhledávání
jsou zde omezené. Výhodou je to, že jsou data stále v jednom úložišti, není třeba
řešit správu (instalaci, konfiguraci nebo zálohování) dalšího nástroje. Ani vývojáři
se nemusí učit nic nového, pouze využijí stávající databázi. Vyhledávání zde probíhá
v nejjednodušší formě pomocí operátoru \verb|LIKE|. Některé databázové systémy
disponují pokročilejšími funkcemi, kterými lze vyhledávání zlepšit \cite{postgres}.
\subsection{Elasticsearch, Apache Solr, Sphinx Search}
Využitím nástrojů přímo určených pro implementaci plnotextového vyhledávání lze
dosáhnout nejlepších výsledků, ať už se jedná o Elasticseacrch či Apache Solr využívající
Apache Lucene \cite{lucene}, nebo Sphinx. Jde o typický krok v okamžiku, kdy
přestává funkčnost relační databáze pro potřeby vyhledávání dostačovat. Tyto nástroje
umožňují pokročilé nastavení indexace a zároveň jsou dostatečně rychlé, aby byly
schopny provádět vyhledávání v řádu milisekund. Výhodou je i cena -- zde uvedené nástroje
jsou poskytovány zdarma, placená bývá až možnost využití podpory nebo rozšiřujících funkcí.
Zřejmou nevýhodou tohoto řešení je nutnost znalosti dalšího nástroje, jeho správa a řešení
synchronizace se stávající databází.
\subsection{Algolia}
Algolia je pokročilý nástroj umožňující imlementaci plnotextového vyhledávání \cite{algolia}.
Zaměřuje se na poskytování kvalitních výsledků v co nejkratším možném čase (v řádu milisekund).
Snaží se usnadnit práci programátorům tím, že nabízí řadu připravených integrací
pro konkrétní programovací jazyky a frameworky. Kromě výsledků vyhledávání umožňuje
faceting, tedy dodání dat pro tvorbu filtrů, podporuje řadu jazyků nebo vyhledávání
podle geografické lokality. V neposlední řadě je k dispozici dashboard zobrazující
stav systému a statistiky vyhledávání.
Pokud si zákazník vystačí s 10 000 vyhledatelnými produkty, může nástroj Algolia používat
zdarma, pouze je povinnen uvést ve výsledcích vyhledávání logo firmy. Placené verze
začínají na 59 dolarech za měsíc za 100 000 produktů.
\subsection{Swiftype Site Search}
Swiftype Site Search je nástroj podobný nástroji Algolia, zaměřuje se však více na
uživatelské rohraní a celkově na snadnost použití \cite{swiftype}. Mezi jeho hlavní
funkce patří vyhledávání v okamžiku formulace hledaného výrazu, možnost filtrace
výsledků, dodatečná úprava pořadí výsledků ručním zásahem na úrovni konkrétních
výsledků, nebo na základě některého z atributů produktu. V nesposlední řadě je také
k dispozici přehledná analytika proběhlého vyhledávání. Cena za provoz služby
je od 299 USD měsíčně.
\subsection{AWS CloudSearch}
Firma Amazon poskytuje v rámci svého cloudu službu CloudSearch \cite{cloud-search}.
Jejími přednostmi jsou především vysoká výkonnost a škálovatelnost. Velkou vstupní
bariérou je však její počáteční složitost. Uživatel musí nejprve proniknout do
některých základních konceptů Amazon Web Services, až poté může začít pracovat
se samotným vyhledáváním. Co se funkčnosti týče, nabízí služba podporu 34 jazyků,
možnost nastavení váhy jednotlivých atributů, nebo doplňování texu během psaní.
Cena záleží na využití výpočetní kapacity, její určení je tedy složitější.
\subsection{Google Custom Search Engine}
Google Custom Search Engine \cite{gse} se nejvíc odlišuje od ostatních služeb.
Vyhledávání je plně řízeno algoritmem společnosti Google a také výsledky vyhledávání
vypadají obdobně jako výsledky vyhledávání na www.google.com.
Odlišné je i samotné napojení na službu -- výsledky vyhledávání jsou na web
vloženy jako samostatná stránka, na které je vidět logo společnosti Google.
Základní varianta je však zdarma, je to tedy levná cesta, jak rychle zprovoznit
vyhledávání na webu. Pokročilejší varianta umožňující konfiguraci stojí 100 USD ročně.
\section{Odůvodnění vytváření nového nástroje}
Výše uvedené nástroje sice umožňují implementaci textového vyhledávání, lze s nimi
dosáhnout dobrých výsledků. Nicméně pokud provozovatel obchodu není ochoten investovat
velké částky do pokročilých řešení, nastává problém. Tento problém je ještě výraznější,
pokud obchod nedisponuje vlastním IT oddělením a pro samotnou implementaci vyhledávání
je vhodné využít minimum času najímaných IT specialistů.
Vzhledem k zjištěným problémům při implementaci textového vyhledávání je očekávaným
přínosem této práce, respektive vzniklé aplikace:
\begin{itemize}
\item Na webu obchodu bude dříve kvalitnější a rychlejší vyhledávání
\item Ryhlejší implementace vyhledávání (pokud ještě na webu žádné není)
\item Vyhledávání může být outsourcováno (úspora nákladů na IT i provoz)
\end{itemize}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Plnotextové vyhledávání}
Tato kapitola popisuje problematiku textového vyhledávání a poukazuje tak na konkrétní
problémy, které je při vyhledávání nutno řešit. Problematika je rozebírána v kontextu
elektronického obchodování, jsou tedy uváděny pouze principy aplikovatelné v tomto
oboru.
Vyhledávání je proces sestávající jednak z ukládání dokumentů určených k~vyhledávání
a dále z provedení vyhledávání uživatelem. Obecné schéma vyhledávání vypadá následovně:
\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{schema-vyhledavani.pdf}
\caption[Proces vyhledávání]{Proces vyhledávání (Zdroj: \cite{searching})}
\label{schema-vyhledavani}
\end{figure}
Ukládání dokumentů probíhá tak, že se upraví pro potřeby vyhledávání a uloží
do indexu, přičemž celý tento proces se označuje jako indexace. Ve chvíli, kdy jsou
dokumenty připraveny k vyhledávání, může uživatel mající potřebu v těchto dokumentech
vyhledávat (získávat z nich informace) formulovat dotaz, kterým chce získat odpovídající
dokumenty. Z něj je vytvořen dotaz, podle nějž bude vyhledávání provedeno. Následně
jsou uživateli dodány dokumenty vyhovující dotazu, ten pak může dotaz na základě
získaných dokumentů a pochopení způsobu vyhledávání dotaz upravit.
\section{Analýza dat, v kterých bude vyhledáváno}
Nejprve je třeba prozkoumat data, ve kterých bude vyhledávání prováděno. Vycházím
ze~skutečnosti, že naprostá většina elektronických obchodů své zboží nabízí také
prostřednictvím srovnávačů zboží, přičemž v počtu návštěv a tedy celkovém provozu
v~rámci českého internetu jsou nejdůležitější Heureka.cz a Zboží.cz \cite{netmonitor}.
Data pro tyto srovnávače musí být dodávána prostředníctvím XML feedu, který odpovídá
specifikaci jednotlivých systémů. Při porovnání obou specifikací lze nalézt
jistou podobnost v požadovaných údajích. Samotný XML feed obsahuje
produkty obchodu, přičemž u každého produktu je možné uvést několik atributů, z~nichž
některé jsou povinné. Konkrétně v případě Zboží.cz musí mít každý produkt uveden název,
popis, URL, cenu a dostupnost. Dále lze využít volitelných parametrů jako název kategorie,
název značky a výrobce, EAN, ISBN, produktový kód výrobce, případně další doplňkové
informace a parametry \cite{xml-zbozi}. V případě Heuréka.cz je podstatný název
obsahující případně výrobce a produktové číslo či kód, název kategorie, dostupnost a
cena dopravy. Informace o produktu mohou dále obsahovat popis, EAN, kód produktu
nebo soupis parametrů \cite{xml-heureka}. Minimální XML soubor s jedním produktem
ve formátu Heuréka je zobrazen ve výpisu \ref{code:xml-heureka}.
\begin{code}
\captionsetup{singlelinecheck=false,justification=raggedright}
\captionof{listing}{Ukázka XML souboru ve formátu Heuréka.cz}
\label{code:xml-heureka}
\begin{minted}{xml}
<?xml version="1.0" encoding="UTF-8"?>
<SHOP>
<SHOPITEM>
<ITEM_ID>40272131</ITEM_ID>
<PRODUCT>
Matrace MYRBACKA - Latexová matrace, střední tvrdost, bílá
</PRODUCT>
<PRODUCTNAME>Matrace MYRBACKA</PRODUCTNAME>
<DESCRIPTION>
<![CDATA[Latex vám umožní lépe odpočívat a to tak, že sleduje
kontury vašeho těla, uvolňuje tlak a poskytuje podporu.
- Potah: 64% polyester, 36% bavlna
- Vnitřní látka: Netkaný polypropylen, 100% jehněčí vlna
- Komfortní materiál: syntetický latex, pěna polyuretan]]>
</DESCRIPTION>
<URL>http://ikea.com/cz/cs/catalog/products/40272</URL>
<IMGURL>http://ikea.com/cz/cs/images/products/40272.JPG</IMGURL>
<PRICE>9087</PRICE>
<PRICE_VAT>10990</PRICE_VAT>
<CATEGORYTEXT>Dům a nábytek | Nábytek | Matrace</CATEGORYTEXT>
<MANUFACTURER>IKEA</MANUFACTURER>
</SHOPITEM>
</SHOP>
\end{minted}
\end{code}
Na základě znalosti struktury XML souboru lze zjistit, že při využití stávajících exportů
internetových obchodů bude každý produkt obsahovat název, popis, URL, cenu, dostupnost
a název kategorie, přičemž pravděpodobně bude k dispozici řada dalších atributů,
dle použitého formátu feedu a dle pečlivosti provozovatele obchodu.
\section{Automatické indexování textů} \label{ch:indexace}
Indexace je proces, kdy jsou ukládány textové dokumenty určené k vyhledání \cite[strana~15]{strossa}.
Ukládány jsou pouze výrazy, podle nichž by měl být ukládaný dokument vyhledatelný,
místo kam jsou tyto výrazy ukládány se nazývá index. Jedná se vlastně o klíče,
podle kterých bude bude možné rychle hledaný záznam nalézt. To je důležité z hlediska
rychlosti vyhledávání -- není možné všechny uložené záznamy procházet a analyzovat
až ve chvíli vyhledávání.
Při indexování je třeba analyzovat každý výraz, který by měl být uložen do indexu.
V prvé řadě je třeba rozhodnout, zda je třeba jej do indexu ukládat, je tedy
třeba řešit významnost jednotlivých výrazů v textu. Pokud daný
výraz není pro vyhledávání užitečný, nemá smysl jej ukládat. Dalším problémem je
tvarosloví, tedy to, že slova mohou měnit tvar (jedná se například o skloňování
podstatných jmen), stále se přitom jedná o jedno slovo. V neposlední řadě je také
třeba zohlednit význam slov v daném oboru, kdy mohou stejná slova vyjadřovat jiné věci
(homonymie -- například myš ve smyslu počítačového příslušenství a myš jako zvíře),
nebo může být jeden význam vyjádřen různými slovy (synonymie -- lednička i chladnička
označuje totéž). Konečně je také třeba brát v úvahu další vztahy mezi slovy,
jako nadřazenost a podřazenost. Například banán a ovoce mohou označovat totéž,
přičemž ovoce to činí v širším slova smyslu, toto označení lze použít i pro jiné
ovoce, například jablko.
\section{Specifika českého jazyka}
Vzhledem k tomu, že je vyhledávání vytvářeno pro české internetové obchody,
bude veškeré vyhledávání probíhat v českém jazyce, a proto nyní popíši jeho specifika.
Český jazyk pracuje se slovy odlišně než jiné jazyky. Dochází i k drobným
odchylkám i v rámci českého jazyka na základě geografické oblasti (nářečí)
nebo na základě zaměření dané skupiny lidí (hantýrka). Dále se můžeme zabývat
grafickou podobou jazyka (morfologií) nebo jeho zvukovou podobou (fonetikou).
Vzhledem k tomu, že vyhledávání probíhá na textové bázi, zabývám se dále právě
grafickou podobou jazyka.
Slova jsou v českém jazyce řazena do slovních druhů, kterých je celkem deset.
Slovní druh pomáhá určit chování slova -- slova stejného slovního druhu se ohýbají
a vyskytují v textu podle podobných pravidel. Slovní druhy lze dělit podle
toho, zda jsou ohebné (tedy zda se jejich tvar může měnit) a neohebné.
Neohebné slovní druhy jsou zpravidla používány ve větě společně s obehnými,
protože samy o sobě nenesou informační hodnotu. Naopak ohebné slovní druhy
samy o sobě nesou informační hodnotu, jsou proto vhodnými kandidáty pro
to, aby se podle nich vyhledávalo. Výjimkou jsou zde zájmena, která nesou
informaci nepřímo.
\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{slovni-druhy.pdf}
\caption{Dělění slovních druhů dle jejich ohebnosti}
\label{slovni-druhy}
\end{figure}
V rámci ohebnosti lze rozlišovat jakým způsobem jsou ohýbána. Slovesa mohou být
časována, příslovce mohou být stupňována, podstatná jména, přídavná jména, zájmena
a číslovky mohou být skloňována. Dále v češtině rozlišujeme tři jmenné rody
(mužský, ženský a střední) a dvě čísla (jednotné a množné). U sloves navíc
rozlišujeme jejich vid.
\section{Problematika tvarosloví}
První problém související s zpracováním přirozeného jazyka je vypořádání se s tvaroslovím
(morfologií). Jednotlivá slova se v českých textech objevují v různých slovních tvarech,
málokdy jsou všechna slova v základním tvaru. Například jeden produkt může mít název
\textbf{Alex Čistič na laminát s pomerančovým olejem} i \textbf{Alex čistič na laminát pomerančový olej}.
V obou případech je uveden \textbf{pomeranč}, jen v různém tvaru. Při vyhledávání je však
žádoucí docílit toho, aby byla obě slova vyhledatelná shodně, ať už bude slovo pomeranč
zadáno v kterémkoli pádě. Typické řešení je vřazení modulu do procesu indexace dokumentů nebo
dotazů, který sjednocuje podobu porovnávaných slov.
\subsection{Základní pojmy tvarosloví}
V této části jsou vysvětlovány základní pojmy rozebíraného oboru. Jejich znalost je nutná k pochopení
následujícího textu. Podrobnější popis těchto termínů lze nalézt v literatuře \cite{strossa}.
\subsubsection*{Morfém}
Morfém je minimální funkční jednotka s vlastním významem. Jde o základní jednotku vědy,
která se zabývá tvorbou slov, tedy morfologie.
\subsubsection*{Lexém}
Lexém je základní stavební jednotka slovníku, znaková jednotka vyjadřující pojem nesoucí
význam. Je to základní jednotka vědy zabývající se slovní zásobou -- lexikologie. Ta je stejně
jako morfologie odvětvím lingvistiky. Každý lexém je pak možné dále dělit na koncovku,
kmen, kořen, prefix a sufix.
\subsubsection*{Foném}
Foném je hláska umožňující rozlišit význam. Obory, pod které spadá, se zabývají zvukovou
stránkou jazyka a nazývají se fonetika a fonologie.
\subsubsection*{Flexe}
Flexe neboli ohýbání popisuje změnu slov vzniklou při skloňování, časování nebo ohýbání.
Jde o grafickou změnu lexému pro vyjádření odpovídajícího pádu, rodu a dalších gramtických
kategorií.
\subsection{Operátor pravostranného rozšíření}
Nejjednodušším řešením problematiky ohýbání slov je operátor pravostranného rozšíření.
Mějme slovo \textbf{svíčka}, které se při skloňování v jednotném čísle mění na svíčky, svíčce,
svíčku, svíčko, svíčce, svíčkou. V tomto příkladu lze vypozorovat, že se mění
pouze konec slova, zatímco levá část \textbf{svíč-} zůstává stejná. Tento přístup bude
sice poměrně úspěšný, nicméně se nevyhneme případům, kdy bude mít více slov stejný
základní tvar. Mohli bychom tak při vyhledání výrazu \textbf{svíčk} obdržet i dokumenty
obsahující slovo \textbf{svíčková}.
Vzhledem k jednoduchosti a zároveň poměrně vysoké úspěšnosti bývá tento přístup
často využíván jako jedna z prvních implementací plnotextového vyhledávání přímo
v relační databázi pomocí operátoru \verb|LIKE|. Konkrétně vyhledávání v jazyce SQL
výše diskutovaného výrazu by bylo provedeno jako \verb|LIKE 'pomeranč%'|.
Kromě problému s možným shodným základem pro různá slova je další komplikací při
použití této metody skutečnost, že při ohýbání slov nedochází pouze ke změně koncovek,
ale často se mění také některá písmena základu slova. Uvažujme slovo \textbf{kůň}, které
má v~druhém pádu podobu \textbf{koně}. Pro tento případ by bylo možné rozšířit možnost
pravostranného rozšíření o nahrazení pouze jednoho znaku. Pokud bychom tak měli
pro nahrazení více písmen využít znak \textbf{*} a pro nahrazení právě jednoho písmene
znak \textbf{?}, byl by základní tvar tohoto slova \textbf{k?ň*}. To je ale problém, protože
takový výraz odpovídá například i slovu \textbf{kaňka}.
\subsection{Derivátor slovních tvarů}
Derivátor slovních tvarů je nástroj, který namísto daného slova vygeneruje
všechny jeho gramatické tvary, případně jeho použitelné odvozeniny.
Ty jsou následně použity jako jejich logická disjunkce. Například místo
slova \verb|svíčka| by se použilo:
\begin{figure}[thp]
\centering
\begin{minipage}{0.73\textwidth}
\begin{minted}{bash}
(svíčky OR svíčce OR svíčku OR svíčko OR svíčkou
OR svíček OR svíčkám OR svíčkami OR svíčkách)
\end{minted}
\end{minipage}
\end{figure}
Takový nástroj musí obsahovat co nejpřesnější sadu pravidel, jak vytvářet
veškeré tvary zadaného slova. Dále je třeba k expandovanému slovu zadat
jeho veškeré informace, aby mohlo být vybráno správné pravidlo.
\subsection{Stematizace}
Stematizace je proces, kdy je slovo převáděno na jeho kmen (stem). Toho je docíleno
odstraněním předpon, přípon a koncovek. Její použití je vhodné pro jazyky,
které mění slova jen tímto způsobem (např. Angličtina). Pro češtinu je však stematizace
hůře aplikovatelná, protože se slova ohýbají podle složitějších pravidel, ne jen
změnou předpon, přípon nebo koncovek. Stematizaci tedy lze využít při hledání základního
tvaru slova i v českém jazyce, je ale nutné ji rozšířit o další procesy, které jsou
popisovány dále.
\subsection{Lematizace}
Lematizátor je nástroj, který převádí slovo na jeho základní gramatický tvar, tzv. lemma.
Základním gramatickým tvarem se rozumí první pád jednotného čísla u podstatných jmen nebo infnitiv
u sloves. Celý proces se nazývá lematizace a kromě převodu na základní tvar může lematizátor
disponovat doplňkovou funkcí, kdy pro daný tvar poskytne i jeho vlastnosti, například
slovní druh, pád nebo číslo. Lematizátor pracuje v podstatě opačně ve srovnání s derivátorem.
Lematizace zároveň není totéž co stematizace, které předpokládá, že dochází
jen k přidávání předpon a přípon. Lematizátor jej vlastně rozšiřuje, odstranění
předpon nebo přípon však může být jednou z jeho činností. Především ale počítá s~tím,
že se koncovky nebo kmeny slov mohou měnit, což je důležité pro češtinu.
Dalším rozdílem je výsledek daného procesu -- po stematizaci může vzniknout díky ořezání
předpon a přípon neexistující slovo, výstupem lematizace je však vždy slovo existující.
Algoritmů pro implementaci lematizátoru je více, triviálním řešením může být použití
slovníku, který obsahuje veškerou slovní zásobu daného jazyka a všechny tvary těchto
slov. V něm je pak nalezeno slovo v daném tvaru a k němu odpovídající základní tvar.
Výhodou takového přístupu je přesnost lematizace, pokud je již daný tvar slova znám,
je triviální najít přesný základní tvar. Jediný problém může způsobit duplicita daného
slova, kdy se musí lematizátor rozhodnout, na který základní tvar jej upraví. Nevýhodou
je poté nutnost vytvoření takového slovníku, kdy je třeba popsat veškerou slovní zásobu.
Další možností je algoritmická lematizace, kdy jsou definována pravidla, podle kterých jsou
slova ohýbána, a ta jsou používána pro hledání základního tvaru. Využití takového přístupu
znamená daleko menší soubor pravidel, podle kterých je lematizace prováděna ve srovnání
s~kompletním slovníkem slovní zásoby. Je tedy rychlejší takový lematizátor vybudovat
od počátku a ve srovnání s použitím slovníku je velká šance, že bude správně zpracováno
neznámé slovo. Pokud chybí ve slovníku, nelze rozhodnout, jak lema vytvořit. Pokud
však budeme mít definovánu jen sadu pravidel, spíše bude lematizace provedena úspěšně.
Zřejmou nevýhodou ve srovnání s využitím slovníku je kvalita takové lematizace.
Čeština je dosti nepravidelná a existuje mnoho výjimek, které se při ohýbání slov vyskytují.
Konečně lze také pro lematizaci využít stochastických metod, respektive metod strojového
učení. Ručně se vytvoří trénovací data, která se následně použijí pro vytvoření modelu.
Na základě tohoto modelu lze provádět samotnou lematizaci, přičemž použitelných metod
strojového učení je celá řada.
\section{Problematika významnosti}
Další problém, který je třeba řešit, je významnost výrazů, podle nichž je vyhledáváno.
Ne všechna slova jsou pro vyhledávání využitelná, protože nenesou žádnou užitečnou
hodnotu, nebo jsou tak častá, že je jejich využití degradováno.
Zároveň však ne všechna slova charakterizují daný dokument stejnou mírou. Nelze se tedy
jen rozhodovat, zda dané slovo ukládat do invertovaného indexu, je také třeba pamatovat
na rozdílnou informační hodnotu slov vůči dokumentům -- ať už se jedná o indexovaný
dokument, nebo o celou jejich sadu.
\subsection{Negativní slovník}
Negativní slovník, někdy označovaný také jako stop-slovník nebo slovník stop-slov,
je datová struktura obsahující slova, která jsou v daném případě považována za bezvýznamná
z pohledu vyhledávání. Bývají to slova určitých slovních druhů, nebo obecně slova, která
nenesou žádný význam. Obvykle jde o předložky, spojky nebo zájmena. Někdy také může jít
o~podstatná jména, která se v~dané oblasti vyskytují tak často, že jsou pro vyhledávání nepoužitelná.
Kromě výše uvedených slovních druhů by také bylo možné použít některá nejčastěji používaná
slova v českém jazyce \cite{nejpouzivanejsi-slova} . Pokud se podíváme na prvních 5 nejpoužívanějších
přídavných jmen (jiný, určitý, další, nový, velký), zjistíme, že právě toto jsou slova,
která pravděpodobně nepůjdou pro vyhledávání dobře použít. Pro vytvoření negativního slovníku
tak bude potřeba existující slovník obsahující slova potřebných slovních druhů a některá tato
nejpoužívanější slova.
Další možností, která může jednoduše vyloučit spojky a předložky, je odfiltrování krátkých
slov. Vzhledem k tomu, že většina takových slov má dělku jeden až dva, nejvýše tři znaky,
je možné to v filtru zohlednit. Hlavní výhodou tohoto přístupu je rychlost oproti vyhledávání
slova v slovníku. Je tedy optimální oba přístupy kombinovat, nejprve odfiltrovat krátká slova
a poté využít slovníku stop-slov, která se tím výrazně zmenší (je možné krátká slova vypustit)
a celá indexace se tím zrychlí.
\subsection{Významnost výrazů}
Důležitá veličina při indexaci výrazu je jeho významnost, neboli míra reprezentace indexovaného
dokumentu. Některé výrazy totiž vystihují daný dokument přesněji než jiné. Uvažujme produkt
s názvem \textbf{Jablko Idared červené}. Slovo \textbf{Jablko} tento produkt vyjadřuje poměrně dobře,
ale stále ještě příliš obecně. Pokud uživatel vyhledává podle tohoto výrazu, stále ještě nelze
rozhodnout, že je tento produkt ten, který hledal. Slovo \textbf{Idared} již reprezentuje konkrétní
produkt daleko přesněji, žádný jiný produkt se takto pravděpodobně nejmenuje. Opakem je pak
slovo \textbf{červené}, které vystihuje produkt nejméně, červené mohou být i jiné potraviny (rajčata)
nebo dokonce úplně jiné produkty (například petrklíč červený).
Z uvedeného příkladu lze vypozorovat, že významnost výrazu souvisí s jeho výskytem v celém
souboru indexovaných dokumentů. Přesněji jde o vztah mezi frekvencí výrazu (TF -- term frequency)
a frekvencí v invertovaných dokumentech (IDF -- inverse document frequency) \cite[strana~21]{strossa}.
Ty lze vypočítat pomocí vzorců:
\[tf(t,d) = 0.5 + 0.5 \cdot \frac{f_{t,d}}{max\{f_{{t}',d}:{t}'\in d\}}\]
\vspace{1mm}
\[idf(t,D)=log \frac{N}{\left | \{d\in D:t\in d\} \right |}\]
\vspace{1mm}
Samotná váha daného výrazu (TF-IDF) \label{tfidf} je definována jako součin těchto hodnot:
\vspace{1mm}
\[tfidf(t,d,D) = tf(t,d) \cdot idf(t,D)\]
\vspace{0mm}
Pro zpřesnění tohoto výpočtu je možné dále pracovat s váhou a to jak u frekvence výrazu,
tak u frekvence v invertovaném indexu. Hodnoty bývají nejčastěji normalizovány nebo
logaritmovány.
\section{Tezaurus}
Tezaurus označuje slovník, který charakterizuje vztahy mezi slovy. Zachycuje podobnost,
nadřazenost nebo podřazenost mezi slovy. Lze jej využít při indexaci nebo formulaci
dotazu a s jeho pomocí je možné daná slova rozšířit o slova s obdobným významem,
přičemž význam může být obecnější nebo naopak přesnější. Tezaurus je díky množství
vztahů které popisuje propracovanější než jen seznam synonym. Lze jej využít
i pro neobvyklá slova, jako je žargón nebo další expresivní výrazy.
Vytvoření takového slovníku je závislé na oblasti, pro kterou je vytvářen. Například
slovo \textbf{oko} bude nahraditelné jinými slovy v kontextu gastronomie a jinými
slovy v oboru biologie. Nelze tedy bezmyšlenkovitě používat jeden takový slovník globálně
pro veškeré vyhledávání, je třeba zohlednit obor, ve kterém bude využíván.
\section{Přibližné vyhledávání}
Dalším komplexním problémem, kterým je třeba se zabývat je přibližné vyhledávání, tedy
vyrovnání se s překlepy nebo schopnost vyhledat dokumenty už v okamžiku, kdy je formulován
vyhledávaný dotaz. Tato funkčnost je označována jako search-as-you-type nebo také
incremental search.
\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{google-preklep.png}
\caption[Odhalení překlepu ve vyhledávání]{Odhalení překlepu ve vyhledávání na webu google.com}
\label{google-preklep}
\end{figure}
U přibližného vyhledávání je třeba se vypořádat s měrou, jak přibližný daný výraz
je vůči výryzu hledanému, což lze vyjádřit pomocí editační vzdálenosti. Přistoupit
k této problematice lze i jednoduším přístupem -- generováním n-gramů.
\subsection{Editační vzdálenost}
Editační vzdálenost je způsob, jak vyjádřit podobnost dvou textových řetězců. Je
vyjádřena jako celé číslo, které udává počet operací nutný pro transformaci z~jednoho
textového řetězce na druhý. Editačních vzdáleností pro textové vyhledávání je více,
podle toho, jaké operace na textovém řetězci umožňují.
V roce 1965 Vladimir Levenshtein definoval \textbf{Levenshteinovu vzdálenost} jako počet
změn znaků vedoucí k transformaci z jednoho textu na druhý \cite{es-fuzziness}:
\begin{itemize}
\item Nahrazení jednoho znaku jiným: \textbf{jxblko} \textrightarrow ~\textbf{jablko}
\item Vložení jednoho znaku: \textbf{jaxblko} \textrightarrow ~\textbf{jablko}
\item Odstranění jednoho znaku: \textbf{jblko} \textrightarrow ~\textbf{jablko}
\end{itemize}
Frederick Damerau ji později rozšířil o další transformaci, která má shodnou váhu:
\begin{itemize}
\item Prohození dvou znaků: \textbf{jbalko} \textrightarrow ~\textbf{jablko}
\end{itemize}
Tato transformace vlastně nahrazuje více dílčích operací definovaných výše.
Vzdálenost s touto transformací o hodnotě 1 je označována jako
\textbf{Damerau–Levenshteinova vzdálenost}.
Počtem transformací se zvyšuje editační vzdálenost a zároveň
s~ní se snižuje pravděpodobnost, že daný textový řetězec je překlepem
druhého řetězce. Damerau vypozoroval, že 80\% překlepů má editační vzdálenost
rovnou jedné \cite{damerau}. Je tedy výrazně nižší pravděpodobnost, že
v textu bude tolik chyb, aby byla vzdálenost vyšší, což lze zohlednit při konstrukci
vyhledávacího algoritmu a bude mít zřejmě pozitivní vliv na rychlost vyhledávání.
Další vzdáleností je \textbf{Hammingova vzdálenost}, která počítá pouze s náhradou
znaku v textovém řetězci. Z tohoto omezení je však patrné, že je použitelná pouze pro
řetězce shodné délky. V praxi textového vyhledávání tedy budeme pracovat pravděpodobně
s~vzdálenostmi definovanými výše.
Na mírně odlišném principu funguje \textbf{vzdálenost nejdelšího společného podřetězce}
(nebo také posloupnosti -- LCS distance). Jejím úkolem je nalézt nejvyšší možný za sebou
jdoucí počet znaků, který je společný oběma řetězcům. Tento přístup je ale méně
chodný pro vyrovnání se s chybami uprostřed slov, navíc je výpočetně náročnější.
Další z možných vzdáleností je \textbf{Jarova vzdálenost}, která kromě počtu
změn na znacích počítá i počet shodných vzdáleností. Jejím rozšířením je
\textbf{Jaro-Winklerova vzdálenost}, která navíc počítá s~tím, že shodnost
na~začátku řetězce má vyšší váhu, než na jeho konci -- vychází
totiž z pozorování, že na začátku textu se vyskytuje méně chyb \cite{christen}.
Tento přístup také dosahuje lepších výsledků u krátkých slov.
\subsection{N-gramová podobnost}
Vytváření n-gramů je používáno při indexaci, kdy jsou slova dělena na části dlouhé \verb|n| znaků.
Pokud bychom měli vygenerovat n-gramy o délce 3 (trigramy) pro slovo \textbf{telefon}, byly by
to výrazy: \textbf{tel}, \textbf{ele}, \textbf{lef}, \textbf{efo} a \textbf{fon}. Lze si
všimnout, že jednotlivé vygenerované výrazy se překrývají. Pokud pak uživatel zadá jako hledaný