BitFunnel

BitFunnel
Разработчики)	Microsoft
Начальная версия	2016 ; 5 лет назад ( 2016 )
Репозиторий	github .com / BitFunnel
Написано в	C ++
Платформа	Windows , macOS , Ubuntu
Тип	Алгоритм индексации поисковой системы
Лицензия	Лицензия MIT
Веб-сайт	bitfunnel .org

BitFunnel - это алгоритм индексации поисковой системы и набор компонентов, используемых в поисковой системе Bing , ^[1] которая была сделана с открытым исходным кодом в 2016 году. ^[2] BitFunnel использует битовые подписи вместо инвертированного индекса в попытке сократить количество операций Стоимость. ^[3]

История [ править ]

Прогресс во внедрении BitFunnel был обнародован в начале 2016 года, и ожидалось, что в том же году появится полезная реализация. ^[4] В сентябре 2016 года исходный код был доступен через GitHub . ^[5] Бумажный обсуждение алгоритма BitFunnel и реализация была выпущена через Special Interest Group по информационному поиску в Ассоциации вычислительной техники в 2017 году и выиграл премию Лучший бумаги. ^[3] ^[6]

Компоненты [ править ]

BitFunnel состоит из трех основных компонентов: ^[1]

BitFunnel - сама система текстового поиска / извлечения
WorkBench - инструмент для подготовки текста для использования в BitFunnel
NativeJIT - программный компонент, который принимает выражения, использующие структуры данных C, и преобразует их в высокооптимизированный ассемблерный код.

Алгоритм [ править ]

Обзор исходной проблемы и решения [ править ]

В документе BitFunnel описывается «проблема соответствия», которая возникает, когда алгоритм должен идентифицировать документы с помощью ключевых слов. Цель проблемы - идентифицировать набор совпадений с учетом корпуса для поиска и запроса ключевых слов для сопоставления. Эта проблема обычно решается с помощью инвертированных индексов , где каждый доступный для поиска элемент поддерживается картой ключевых слов. ^[3]

Напротив, BitFunnel представляет каждый доступный для поиска элемент с помощью подписи. Подпись - это последовательность битов, которые описывают фильтр Блума доступных для поиска терминов в данном доступном для поиска элементе. Фильтр Блума создается путем хеширования через несколько битовых позиций. ^[3]

Теоретическая реализация сигнатур битовой строки [ править ]

Подпись документа (D) может быть описана как логическая или из его срочных подписей:

${\overrightarrow {S_{D}}}=\bigcup \limits _{t\in D}{\overrightarrow {S_{t}}}$

Точно так же запрос документа (Q) можно определить как объединение:

${\overrightarrow {S_{Q}}}=\bigcup \limits _{t\in Q}{\overrightarrow {S_{t}}}$

Кроме того, документ D является членом множества M ', если выполняется следующее условие:

${\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}$

Затем эти знания объединяются для создания формулы, в которой M ' идентифицируется документами, соответствующими сигнатуре запроса:

$M'=\{D\in C|{\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}\}$

Эти шаги и их доказательства обсуждаются в статье 2017 года. ^[3]

Псевдокод для сигнатур битовой строки [ править ]

Этот алгоритм описан в статье 2017 года. ^[3]

{\begin{array}{l}M'=\emptyset \\{\texttt {for}}\ {\texttt {all}}\ D\in C\ {\texttt {do}}\\\qquad {\texttt {if}}\ {\overrightarrow {S_{D}}}\cap {\overrightarrow {S_{Q}}}={\overrightarrow {S_{Q}}}\ {\texttt {then}}\\\qquad \qquad M'=M'\cup \{D\}\\\qquad {\texttt {endif}}\\{\texttt {endfor}}\end{array}}

Ссылки [ править ]

^ Б Yegulalp, Сердар (6 сентября 2016). «Компоненты Microsoft Bing с открытым исходным кодом для быстрой компиляции кода» . InfoWorld .
^ Верма, Arpit (2016-09-07). «Основные компоненты поисковой системы Bing с открытым исходным кодом Microsoft, вот почему это важно» . Fossbytes . Проверено 12 июня 2020 .
^ Б с д е е Goodwin, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Эльникети, Самех; Он, Юйсюн (2017-08-07). «BitFunnel» . Материалы 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска . Нью-Йорк, Нью-Йорк, США: ACM: 605–614. DOI : 10.1145 / 3077136.3080789 . ISBN 978-1-4503-5022-8.
^ «Когда можно будет использовать BitFunnel? · BitFunnel» . bitfunnel.org . Проверено 12 июня 2020 .
^ BitFunnel / BitFunnel , BitFunnel, 12 мая 2020 г. , получено 12 июня 2020 г.
^ "SIGIR Best Paper Awards" . ACM . Проверено 8 июля 2020 .

Внешние ссылки [ править ]

BitFunnel · GitHub
BitFunnel · BitFunnel

[InfoWorld-1] Б Yegulalp, Сердар (6 сентября 2016). «Компоненты Microsoft Bing с открытым исходным кодом для быстрой компиляции кода» . InfoWorld .

[2] Верма, Arpit (2016-09-07). «Основные компоненты поисковой системы Bing с открытым исходным кодом Microsoft, вот почему это важно» . Fossbytes . Проверено 12 июня 2020 .

[:0-3] Б с д е е Goodwin, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Эльникети, Самех; Он, Юйсюн (2017-08-07). «BitFunnel» . Материалы 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска . Нью-Йорк, Нью-Йорк, США: ACM: 605–614. DOI : 10.1145 / 3077136.3080789 . ISBN 978-1-4503-5022-8.

[4] «Когда можно будет использовать BitFunnel? · BitFunnel» . bitfunnel.org . Проверено 12 июня 2020 .

[5] BitFunnel / BitFunnel , BitFunnel, 12 мая 2020 г. , получено 12 июня 2020 г.

[6] "SIGIR Best Paper Awards" . ACM . Проверено 8 июля 2020 .

[1]