Электронные лекции (1176816)
Текст из файла
Ìîñêîâñêèé Ãîñóäàðñòâåííûé Óíèâåðñèòåò èì. Ì.Â.ËîìîíîñîâàÔàêóëüòåò Âû÷èñëèòåëüíîé Ìàòåìàòèêè è ÊèáåðíåòèêèÊîíñïåêò ëåêöèé ïî êóðñóÂâåäåíèå â èíôîðìàöèîííûé ïîèñêÑîñòàâèë:ñòóäåíò 520 ãðóïïûÍîêåëü Ìèõàèë Àëåêñååâè÷Ìîñêâà, 2010 ã.Ñîäåðæàíèå1Ëåêöèÿ 322Ëåêöèÿ 5. Ëèíãâèñòè÷åñêèå òåõíîëîãèè â èíôîðìàöèîííîì ïîèñêå43Ëåêöèÿ 6. Ìîäåëè èíôîðìàöèîííîãî ïîèñêà74Ëåêöèÿ 7.
Âîïðîñíî-îòâåòíûå ñèñòåìû105Ëåêöèÿ 8. Ïîèñê ïî èçîáðàæåíèÿì126Ëåêöèÿ 9165.15.26.1Îöåíêà êà÷åñòâà èíôîðìàöèîííîãî ïîèñêà . . . . . . . . . . . . . . 13×èñëåííûå ìåòîäû îöåíêè èíôîðìàöèîííîãî ïîèñêà . . . . . . . . 15Ïîèñêîâàÿ îïòèìèçàöèÿ è ìåòîäû áîðüáû ñ íåé . . . . . . . . . .
. 171Ëåêöèÿ 327 îêòÿáðÿ 2010 ã.Ïðèâåä¼ì âíà÷àëå íåñêîëüêî òåðìèíîâ.Äëÿ êàæäîãî òåðìèíà êîîðäèíàòíûé èíäåêñ õðàíèò ïåðå÷åíü âñåõ ïîçèöèé,ãäå îí âñòðåòèëñÿ â äîêóìåíòå.Ëåêñåìà ýêçåìïëÿð ïîñëåäîâàòåëüíîñòè ñèìâîëîâ â äîêóìåíòå, îáúåäèí¼ííîé â ñèíòàêñè÷åñêóþ åäèíèöó äëÿ ðàçáîðà.Òèï êëàññ âñåõ îäèíàêîâûõ ëåêñåì.Òåðìèí òèï, âêëþ÷¼ííûé â ñëîâàðü èíôîðìàöèîííîãî ïîèñêà.Ëåêñèêîí ìíîæåñòâî âñåõ òåðìèíîâ, âêëþ÷¼ííûõ â ñëîâàðü ñèñòåìû èíôîðìàöèîííîãî ïîèñêà.Îáùàÿ çàäà÷à ó íàñ òàêîâà: íà âõîä ïîäà¼òñÿ ïîñëåäîâàòåëüíîñòü ñèìâîëîâ, êîòîðóþ íàäî ðàçáèòü íà îòäåëüíûå ëåêñåìû (â ïðîñòåéøåì ñëó÷àå íàñëîâà).
Ñëîâà çàòåì âûäåëÿþòñÿ â ñëîâîôîðìû. Òàêæå î÷åíü âàæíî õðàíèòüèíôîðìàöèþ î òîì, â êàêîì ïàäåæå è â êàêîì ìåñòå âñòðåòèëîñü ñëîâî.Îñíîâíûå àëãîðèòìû1 :• Ïîñòðîåíèå èíäåêñà ñîðòèðîâêîé è ãðóïïèðîâêîé. Ýòî ïðîñòåéøèé àëãîðèòì. Âõîäíûå äàííûå (ïîëó÷àþòñÿ ïðè ðàçáîðå ääîêóìåíòîâ): òåðìèíûè ñîîòâåòñòâóþùèå èì èäåíòèôèêàòîðû äîêóìåíòîâ, â êîòîðîì îíè âñòðåòèëèñü.
Îñíîâíûå ñòàäèè òàêîâû:1. Àëôàâèòíîå óïîðÿäî÷èâàíèå èëè ëåêñèêî-ãðàôè÷åñêàÿ ñîðòèðîâêà2. Ãðóïïèðîâêà2Íàäî áû åù¼ ó÷åñòü è òî, êàê ýòè àëãîðèòìû ðàáîòàþò íà êîíêðåòíîìàïïàðàòíîì îáåñïå÷åíèè (îñîáåííî ââèäó áîëüøîãî îáú¼ìà äàííûõ). Îñîáåííîñòè àïïàðàòíîãî îáåñïå÷åíèÿ òàêîâû:1. Äîñòóï ê äàííûì â ïàìÿòè ãîðàçäî áûñòðåå, ÷åì ê äàííûì íà äèñêå.×àñòî èñïîëüçóåìûå äàííûå äîëæíû õðàíèòüñÿ â êåøå, ïàìÿòè, äèñêîâîì êåøå. Ê ñâåäåíèþ, ó êðóïíûõ ïîèñêîâûõ ñèñòåì âñå èíäåêñûõðàíÿòñÿ â îïåðàòèâíîé ïàìÿòè. Ïðè ÷¼ì èíäåêñû ðàñïðåäåë¼ííûå íà êàæäîé ìàøèíå õðàíèòñÿ ëèøü ÷àñòü èíäåêñà.2. Ñïåöèôè÷íûå ñâîéñòâà äèñêà: äàííûå õðàíÿòñÿ áëîêàìè. Åñëè íàäîïðî÷èòàòü èíôîðìàöèþ ñ äèñêà, òî ÷èòàþòñÿ âñå äàííûå èç áëîêà.Äî ýòîãî åù¼ íàäî åù¼ ñïîçèöèîíèðîâàòü ìàãíèòíóþ ãîëîâêó äèñêà.Ýòî âñ¼ âðåìÿ, ìíîãî âðåìåíè.3.
Ïðè ðàáîòå ñ æ¼ñòêèì äèñêîì òîæå åñòü êåø, îñîáåííîñòè êîòîðîãîìîãóò ïîâëèÿòü íà ïðîèçâîäèòåëüíîñòü.4. ×åì áûñòðåå ïàìÿòü, òåì å¼ ìåíüøå, è íàîáîðîò. Êåøà ìåíüøå îïåðàòèâíîé ïàìÿòè, îïåðàòèâíîé ïàìÿòè ìåíüøå, ÷åì äèñêîâîé. Íî åñòüè èñêëþ÷åíèå êåø äèñêîâîé ïàìÿòè ìåíüøå îïåðàòèâíîé ïàìÿòè.1 Âìåñòî òåðìèíà èñïîëüçóåòñÿ ïîíÿòèå èäåíòèôèêàòîðà2 Õðàíèòñÿ òàêæå åù¼ è êó÷à äîïîëíèòåëüíûõ ïàðàìåòðîâ òåðìèíîâ(óêàçàíèå êîíòåêñòà,ïàäåæà)25. Íà ïðîöåññîðå ÷òî-òî ñ÷èòàåòñÿ, à ïàìÿòü îáìåíèâàåòñÿ äàííûìè ñäèñêîì → íåò ïðîñòîÿ ñèñòåìû.• Áëî÷íîå èíäåêñèðîâàíèå, îñíîâàííîå íà ñîðòèðîâêå (BSBI). Åñëè âñå äàííûå íå ïîìåùàþòñÿ â ïàìÿòè, òî èõ íàäî ðàçäåëèòü íà áëîêè, êîòîðûåïîìåùàþòñÿ, îáðàáîòàòü áëîêè è ïîòîì îáúåäèíèòü.
Ó ýòîãî àëãîðèòìàìíîãî îáùåãî ñ ñîðòèðîâêîé ñëèÿíèåì. Îñíîâíûå ñòàäèè ðàáîòû àëãîðèòìà òàêîâû:1. Ðàçäåëåíèå íà ÷àñòè èëè ñåãìåíòàöèÿ êîëëåêöèè2. Ñîðòèðîâêà ïàðû òåðìèí-èäåíòèôèêàòîð äîêóìåíòà (àíàëîãè÷íî ïðîñòåéøåìó àëãîðèòìó)3. Çàïèñü îòñîðòèðîâàííûõ áëîêîâ íà äèñê4. Îáúåäèíåíèå âñåõ ïîëó÷èâøèõñÿ áëîêîâ, èõ ñëèÿíèå. Òåì ñàìûì ïîëó÷àåì îáùèé èíâåðòèðîâàííûé èíäåêñÁëîêè, êàê ïðàâèëî, âûáèðàþòñÿ îäèíàêîâîãî ðàçìåðà.
Äëÿ êàæäîãî áëîêà ñòðîèòñÿ ñâîé èíâåðòèðîâàííûé èíäåêñ, êîòîðûé ïîòîì çàïèñûâàåòñÿ âîòäåëüíûé ôàéë. À â êîíöå ðàáîòû àëãîðèòìà ýòè èíäåêñû îáúåäèíÿþòñÿè íà äèñê çàïèñûâàåòñÿ èòîãîâûé ôàéë. Ïðè ýòîì îáðàáîòêà ìîæåò èäòèïàðàëëåëüíî äëÿ êàæäîãî áëîêà.  êà÷åñòâå äîïîëíèòåëüíîé èíôîðìàöèè äëÿ òåðìèíîâ ìîãóò çàïèñûâàòüñÿ ðàçëè÷íûå õàðàêòåðèñòèêè (â òîì÷èñëå è ÿçûêîâûå).• Îäíîïðîõîäíîå èíäåêñèðîâàíèå â îïåðàòèâíîé ïàìÿòè (SPIMI).
Çäåñü èñïîëüçóþòñÿ òåðìèíû, à íå èäåíòèôèêàòîðû. Òàêæå íå èñïîëüçóåòñÿ îáùèéñëîâàðü äëÿ âñåõ òåðìèíîâ, à äëÿ êàæäîãî áëîêà äèíàìè÷åñêè ñòðîèòñÿñâîé ñëîâàðü. Åñëè òåðìèí åñòü â ñëîâàðå, òî èíôîðìàöèÿ î í¼ì äîáàâëÿåòñÿ ê ñóùåñòâóþùåé. Åñëè æå òåðìèí âñòðå÷àåòñÿ â ïåðâûé ðàç, òîîí äîáàâëÿåòñÿ â ñëîâàðü, è íîâûå âõîæäåíèÿ äàííîãî òåðìèíà áóäóò çàïèñûâàòüñÿ èìåííî ñþäà3 . Âñå ýòè îñîáåííîñòè ïîçâîëÿþò ýêîíîìèòü ïàìÿòü ïî ñðàâíåíèþ ñ ïðåäûäóùèìè âàðèàíòàìè. Îò ñîðòèðîâêè, ïðèñóùåéïðîøëîìó àëãîðèòìó, ìîæíî èçáàâèòüñÿ, ïîñêîëüêó êàæäûé ðàç, êîãäàâñòðå÷àåòñÿ ñëîâî, óæå èçâåñòíî, êóäà åãî çàïèñûâàòü. Òàê êàê êîëè÷åñòâî âñòðå÷ êîíêðåòíîãî ñëîâà íå ïðåâîñõîäèò ÷èñëà ñëîâ â äîêóìåíòå, òîèç-çà îòñóòñòâèÿ ñîðòèðîâêè äîñòèãàåòñÿ ïðèëè÷íàÿ ýêîíîìèÿ.Åù¼ îäíà îñîáåííîñòü: åñëè ïàìÿòü çàêîí÷èâàåòñÿ, òî çàêàí÷èâàåì îáðàáàòûâàòü òåêóùèé áëîê, áåð¼ì ñëåäóþùèé è íà÷èíàåì ñòðîèòü íîâûéèíâåðòèðîâàííûé èíäåêñ äëÿ íåãî.
Îáúåäèíåíèå áëîêîâ ïðîèñõîäèò àíàëîãè÷íî ïðåäûäóùåìó àëãîðèòìó, çà èñêëþ÷åíèåì òîãî, ÷òî ñëèâàþòñÿ íåòîëüêî ñëîâà, íî è ñëîâàðè.×òî äåëàòü â ñëó÷àå, åñëè äîêóìåíòû ìåíÿþòñÿ (êàê è ñàìè äîêóìåíòû,òàê è èõ êîëè÷åñòâî)? Ïðåäûäóùèå àëãîðèòìû ðàññìàòðèâàþò ëèøü ñòàòèêó,3 Íàäî ó÷åñòü, ÷òî ñëîâàðü ðåàëèçóåòñÿ â âèäå õåøàíîñòüþ.3→ âîçíèêàþò ïðîáëåìû ñ óïîðÿäî÷åí-íî íå äèíàìèêó.  ïîñëåäíåì ñëó÷àå íàäî êàê-òî îáíîâëÿòü èíäåêñ. Ñàìûéïðîñòåøèé ñïîñîá, êîòîðûé ïðèõîäèò â ãîëîâó, - ýòî íå ïðàâêà èíäåêñà (èáîýòî î÷åíü äîðîãàÿ îïåðàöèÿ, ïîñêîëüêó íàäî äâèãàòü òåñíî óêîìïëåêòîâàííûåáëîêè), à ïåðåñòðîåíèå èíäåêñà (ýòèì ìåòîäîì ïîëüçóþòñÿ è êðóïíûå ïîèñêîâûåñèñòåìû).Äðóãîé ïîäõîä çàêëþ÷àåòñÿ â ïîñòðîåíèè âñïîìîãàòåëüíîãî èíäåêñà (äîïîëíèòåëüíîãî èëè èíäåêñà îáíîâëåíèÿ).
Äëÿ îáðàáîòêè çàïðîñà èñïîëüçóþòñÿ èîñíîâíîé, è âñïîìîãàòåëüíûé èíäåñû, à ðåçóëüòàòû îáúåäèíÿþòñÿ. Êîãäà âñïîìîãàòåëüíûé èíäåêñ ðàçðàñòàåòñÿ, íàäî ïðîâîäèòü ñëèÿíèå äâóõ èíäåêñîâ. Íîýòó îïåðàöèþ ìîæíî òðàêòîâàòü è êàê ïåðåñòðîåíèå èíäåêñà.Êàê áûòü, åñëè äîêóìåíò óñòàðåë èëè áûë óäàë¼í? Èç-çà òîãî, ÷òî åñòü äîïîëíèòåëüíàÿ èíôîðìàöèÿ, òî ìîæíî ïîñòàâèòü ôëàã îá ýòîì. Íî, ê ïðèìåðó,ó ßíäåêñà åñòü ñåðâèñ äëÿ RSS-ïîòîêîâ, â àðõèâå êîòîðîãî óäàë¼ííàÿ èíôîðìàöèÿ îñòà¼òñÿ.Åñòü òàêæå ïðîáëåìà áåçîïàñíîñòè èíäåêñà. Êîìó-òî èíôîðìàöèÿ äîñòóïíà, êîìó-òî íåò. Ïðèìåð: ïîèñê â êîðïîðàòèâíîé ñðåäå.
Ïðåäïîëîæèì, ÷òî óíàñ åñòü ðàçíûå äîêóìåíòû ðàçíîãî óðîâíÿ äîñòóïà, ê êîòîðûì åñòü äîñòóï óðàçíûõ ïîëüçîâàòåëåé. Êàê îáåñïå÷èòü ðåëåâàíòíóþ âûäà÷ó ðåçóëüòàòîâ? Åñëèåñòü äîñòóï ó ïîëüçîâàòåëÿ, òî âêëþ÷àåì â ðåçóëüòàòû âûäà÷è, èíà÷å - íåò (âýòîì ñëó÷àå ïîëüçîâàòåëü äàæå íå çíàåò î ñóùåñòâîâàíèè äîêóìåíòà). Ðåàëüíûå ïðèìåðû: çàêðûòûå ñåòè Îäíîêëàññíèêè, Êîíòàêò. Äëÿ ðåàëèçàöèè ýòîãîìåõàíèçìà èñïîëüçóþòñÿ ñïèñêè êîíòðîëÿ äîñòóïà (ACL).Ïîãîâîðèì òåïåðü ïðî ñæàòèå. Õîòåëîñü áû áîëüøå äàííûõ â ïàìÿòè ðàçìåùàòü → äëÿ ýòîãî íàäî ñæèìàòü èõ. Åñòü ïðîñòåéøèå ìåòîäû ñæàòèÿ, èäåÿêîòîðûõ ïîäñ÷èòàòü ñêîëüêî ðàç ñëîâî âñòðåòèëîñü, çàïèñàòü ýòî ÷èñëî è 1 ðàçíàïèñàòü, ÷òî ýòî çà ñëîâî. Ýòîò ìåòîä ñæàòèÿ íåòðóäî¼ìêèé è äà¼ò ïðèëè÷íûéâûèãðûø.2Ëåêöèÿ 5.
Ëèíãâèñòè÷åñêèå òåõíîëîãèè â èíôîðìàöèîííîì ïîèñêå24 íîÿáðÿ 2010 ã.Ýòàïû ëèíãâèñòè÷åñêîãî àíàëèçà (îò ïðîñòîãî ê ñëîæíîìó)4 :1. Ãðàôåìàòè÷åñêèé àíàëèç (òîêåíèçàöèÿ)2. Ìîðôîëîãè÷åñêèé àíàëèç3. Ñèíòàêñè÷åñêèé àíàëèç4. Ñåìàíòè÷åñêèé àíàëèç5. Ïðàãìàòè÷åñêèé àíàëèç4  ðàçíîé ëèòåðàòóðå ðàçíûå íàçâàíèÿ ýòàïîâ, à íåêîòîðûå (íàïðèìåð, ãðàôåìàòè÷åñêèé èìîðôîëîãè÷åñêèé - äîïðàãìàòè÷åñêèé àíàëèç) îáúåäèíÿþòñÿ. Äëÿ èíôîðìàöèîííîãî ïîèñêààêòóàëüíûå ïåðâûå äâà ýòàïà4Ïî÷òè âñ¼ â web ïåðåäà¼òñÿ ïî ïðîòîêîëó ãèïåðòåêñòà, ïîýòîìó â òåêñòå ñîäåðæàòñÿ, â ÷àñòíîñòè, òèïû MIME.
Ñóùåñòâóåò íåñêîëüêî ðàçíûõ êëàññîâ òèïîâ,íî íàñ èíòåðåñóþò: text è application (ïëîñêèé òåêñò, òåêñòû ðàçìåòêè, pdf è ïðî÷èå .doc ôàéîû). Íà ýòàïå èçâëå÷åíèÿ èíôîðìàöèè ïîëó÷àåòñÿ ïëîñêèé òåêñò(âîçìîæíî, ñ ñîõðàíåíèåì ôîðìàòèðîâàíèÿ). ×òî êàñàåòñÿ òåêñòîâ ðàçìåòêè,òàì ñîäåðæàòñÿ ñïåöèàëüíûå òåãè: äëÿ îïðåäåëåíèÿ ÿçûêà è ò.ï. Ïîìèìî ôîðìàòà íàäî îïðåäåëèòü ÿçûê è êîäèðîâêó - ìîæåò áûòü ÿâíî ñêàçàíî, à ìîæåòáûòü è íåò → íàäî îïðåäåëÿòü ñàìîìó òîãäà.Îñíîâíûå ñïîñîáû èõ îïðåäåëåíèÿ:1. Ñëîâàðíûå ìåòîäû (ðåäêî èñïîëüçóþòñÿ íà ïðàêòèêå)2. Ñòàòèñòè÷åñêèå ìåòîäû (ñîïîñòàâëåíèå êîäîâ ñèìâîëîâ).
Îñíîâàíû íà ñîâìåñòíîé âñòðå÷àåìîñòè áóêâ. Îñíîâûâàÿñü íà ýòîì è íà çíàíèè òàêèõðàñïðåäåëåíèé, ìîæíî îïðåäåëÿòü ÿçûê.  îñíîâíîì ñ÷èòàåòñÿ íà îñíîâå òðèãðàìì (òðîåê ñèìâîëîâ). Íà èõ îñíîâå îñóùåñòâëÿåòñÿ îïðåäåëåíèåÿçûêà âî âñåõ ñîâðåìåííûõ áðàóçåðàõ. Íåäîñòàòêè: åñëè ìàëî äàííûõ, òîíå ðàáîòàåò. Ïðèìåð: åñëè áðàóçåð íà êîðîòêèõ òåêñòàõ îøèáàåòñÿ, òî îíâûäà¼ò òóðåöêèé ÿçûê (à íå ðóññêèé).Òåïåðü óæå ìîæíî ïåðåõîäèòü ê ëèíãâèñòè÷åñêèì âîïðîñàì. Íà âõîäå: ïîòîêñèìâîëîâ, äëÿ êîòîðûõ èçâåñòíû ÿçûê è êîäèðîâêà (îò ôîðìàòîâ óæå èçáàâèëèñü).Íàïîìíèì îïðåäåëåíèÿ, ââåä¼ííûå ðàíüøå.Ëåêñåìà (òîêåí) - ýêçåìïëÿð ïîñëåäîâàòåëüíîñòè ñèìâîëîâ, ïðåäñòàâëÿþùèõ ñåìàíòè÷åñêóþ åäèíèöó äëÿ îáðàáîòêè òåêñòàÒèï - íàáîð ëåêñåì, îáëàäàþùèõ îïðåäåë¼ííûìè ñâîéñòâàìè.Íàïðèìåð, Ty-154 - ýòî ëèáî äâà, ëèáî òðè òîêåíà (çàâèñèò îò ñèñòåìû).Íåîáõîäèìî ýòîò ïîòîê ñèìâîëîâ ïîáèòü íà ëåêñåìû (òîêåíû).
Ââåä¼ì äâàíåýêâèâàëåíòíûõ îïðåäåëåíèÿ:Ëåêñåìà (òîêåí) - ýòî ïîñëåäîâàòåëüíîñòü ñèìâîëîâ ìåæäó äâóìÿ ðàçäåëèòåëÿìè.Ðàçäåëèòåëü - ïðîáåë, ïåðåâîä ñòðîêè, âîçâðàò êàðåòêè, òàáóëÿöèÿ, çíàêèïðåïèíàíèÿ (íî èíîãäà ó÷èòûâàþòñÿ - â çàâèñèìîñòè îò òîãî, êàê ôîðìèðóþòñÿñëîâàðè) è ñëóæåáíûå ñèìâîëû (íàïðèìåð, Ñ++). Òî÷êè ìîãóò áûòü ðàçäåëèòåëÿìè, à ìîãóò è íå áûòü (ïðèìåð: À.Ñ.Ïóøêèí).Äàëåå ñëåäóåò ìîðôîëîãè÷åñêèé àíàëèç.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
