Ақпаратты іздеу жүйесі: Бульдік модель негізгі ұғымдары, құжаттар мен сұранымдар жиынтығы ретінде қарастырылады. Іздеу логикалық операторлармен жүзеге асырылады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Классикалық ақпаратты іздеу моделі
Classical information retrieval model
(Стандартты) Бульдік ақпаратты іздеу моделі (BIR) – классикалық ақпаратты іздеу (IR) моделі және сонымен бірге, алғашқы және ең көп қолданылатын модель. BIR Буль логикасы мен классикалық жиын теориясына негізделген, себебі ізделінетін құжаттар мен пайдаланушының сұранысы терминдер жиынтығы ретінде қарастырылады (сөздер жинағы моделі). Іздеу нәтижелері құжаттарда сұраныс терминдерінің болуына және сұраныста сипатталған Бульдік шарттардың орындалуына байланысты болады.
The (standard) Boolean model of information retrieval (BIR) is a classical information retrieval (IR) model and, at the same time, the first and most adopted one. The BIR is based on Boolean logic and classical set theory in that both the documents to be searched and the user's query are conceived as sets of terms (a bag of words model). Retrieval is based on whether or not the documents contain the query terms and whether they satisfy the boolean conditions described by the query.
Анықтамалар
Индекс термині – құжатты сипаттайтын немесе мінелейтін сөз немесе тіркес, мысалы, журнал мақаласы үшін берілген кілт сөз. Барлық мұндай индекс терминдерінің жиынтығы L болсын. Құжат – L жиынтығының кез келген ішкі жиыны. Сұрау – нормалды түріндегі Бульдік өрнек: , мұнда үшін дұрыс, егер (Бұл эквивалентті түрде дизъюнктивті нормалды түрде де көрсетілуі мүмкін). Біз сұрауды қанағаттандыратын құжаттар жиынтығын табуға тырысамыз. Бұл операция іздеу деп аталады және келесі екі қадамнан тұрады:
An index term is a word or expression, which may be stemmed, describing or characterizing a document, such as a keyword given for a journal article. Letbe the set of all such index terms. A document is any subset of Letbe the set of all documents. A query is a Boolean expression in normal form:where is true for when (Equivalently, could be expressed in disjunctive normal form.) We seek to find the set of documents that satisfy This operation is called retrieval and consists of the following two steps:
1. Әрбір i үшін : талапқа сай келетін құжаттар жиынтығын табыңыз.
2. Содан кейін Q сұрауын қанағаттандыратын құжаттар жиынтығы мына формуламен беріледі:
1. For each in , find the set of documents that satisfy :2. Then the set of documents that satisfy Q is given by:
Деректер құрылымы мен алгоритмдер
Тек формальды математикалық тұрғыдан қарағанда, BIR түзу. Бірақ, практикалық тұрғыдан алғанда, алгоритмдер мен дерек құрылымдарына қатысты қосымша бірнеше мәселелерді шешу қажет, мысалы, терминдерді таңдау (қолмен немесе автоматты түрде таңдау, немесе екеуінің де үйлесімі), түбірге келтіру, хэш-кестелер, инверттік файл құрылымы және тағы да басқалар.
From a pure formal mathematical point of view, the BIR is straightforward. From a practical point of view, however, several further problems should be solved that relate to algorithms and data structures, such as, for example, the choice of terms (manual or automatic selection or both), stemming, hash tables, inverted file structure, and so on.
Хаш сеттер
Тағы бір мүмкіндік – хэш жиынтықтарын пайдалану. Әрбір құжат сол құжаттағы барлық сөздерді қамтитын хэш-кесте арқылы көрсетіледі. Хэш-кестенің мөлшері сөздерді қосу және жою арқылы нақты уақытта өсіп, кемитіндіктен, әрбір құжат жадта әлдеқайда аз орын алады. Дегенмен, операциялар биттік векторларға қарағанда күрделі болғандықтан, өнімділік төмендеуі мүмкін. Ең жаман жағдайда өнімділік O(n)-ден O(n²) дейін нашарлауы мүмкін. Ал орташа жағдайда өнімділік төмендеуі биттік векторларға қарағанда айтарлықтай болмайды және жадты пайдалану әлдеқайда тиімді.
Another possibility is to use hash sets. Each document is represented by a hash table which contains every single term of that document. Since hash table size increases and decreases in real time with the addition and removal of terms, each document will occupy much less space in memory. However, it will have a slowdown in performance because the operations are more complex than with bit vectors. On the worst case performance can degrade from O(n) to O(n2). On the average case, the performance slowdown will not be that much worse than bit vectors and the space usage is much more efficient.
Қолтаңба файлы
Әрбір құжатты құжаттағы сөздер жиынтығын көрсететін Блум сүзгісі арқылы қорытындылауға болады, ол "қолтаңба" деп аталатын белгілі бір ұзындықтағы биттер тізбегінде сақталады. Қолтаңба файлында жинақтағы әрбір құжат үшін мұндай біріктірілген кодтық биттер тізбегі болады. Әрбір сұранысты да сұраныстағы сөздер жиынтығын көрсететін Блум сүзгісімен қорытындылауға болады, ол сол ұзындықтағы биттер тізбегінде сақталады. Сұраныс тізбегі әрбір қолтаңбамен тексеріледі. Бұл қолтаңба файлы BitFunnel жүйесінде қолданылады.
Each document can be summarized by Bloom filter representing the set of words in that document, stored in a fixed length bitstring, called a signature. The signature file contains one such superimposed code bitstring for every document in the collection. Each query can also be summarized by a Bloom filter representing the set of words in the query, stored in a bitstring of the same fixed length. The query bitstring is tested against each signature. The signature file approached is used in BitFunnel.