Kiba>> elasticsearch7-ngrams-fuzzy-shingles-stemming-workshop>> 返回
项目作者： mtumilowicz

项目描述 ：
Gentle introduction to basic elasticsearch constructs boosting search: ngrams, shingles, stemmers, suggesters and fuzzy queries.
高级语言：
项目地址: git://github.com/mtumilowicz/elasticsearch7-ngrams-fuzzy-shingles-stemming-workshop.git
创建时间： 2020-05-08T17:03:02Z
项目社区：https://github.com/mtumilowicz/elasticsearch7-ngrams-fuzzy-shingles-stemming-workshop
开源协议：GNU General Public License v3.0
下载


License: GPL v3

elasticsearch7-ngrams-fuzzy-shingles-stemming-workshop

preface

  • goals of this workshop
    • introduction to typos and suggestions handling in elasticsearch
    • introduction to basic constructs boosting search
      • ngram and edge ngram (typos, prefixes)
      • shingles (phrase)
      • stemmers (operating on roots rather than words)
      • fuzzy queries (typos)
      • suggesters
  • in docker-compose there is elasticsearch + kibana (7.6) prepared for local testing
    • cd docker/compose
    • docker-compose up -d
  • workshop and answers are in workshop directory

introduction

  • searching natural language is inherently imprecise - computers can’t comprehend natural language
    • they need heuristic, an algorithmic equivalent of true linguistic comprehension
  • Lucene is composed of many text processing tools
    • example: prefix query
      • simply matches the beginning letters of words
    • example: fuzzy queries
      • find words that need at most a certain number of ‘edits’, to match the query
    • example: snowball stemmer and the metaphone phonetic analyzer
      • mimic grammatical and phonetic aspects of language
    • example: autocomplete functionality (other names: search as you type, type-ahead search)

ngram

  • splitting a token into multiple subtokens
  • sliding window that moves across the word - continuous sequence of characters of the specified length
  • example
    • token: pillar
    • 1-grams: p, i, l, l, a, r
    • bigrams: pi, il, ll, la, ar
    • trigrams: pil, ill, lla, lar
  • how it could boost searching of incorrectly spelled word
    • search: “pilar”
    • bigrams for “pillar”: pi, il, ll, la, ar
    • bigrams for “pilar”: pi, il, la, ar
      • 4/5 match comparing to correctly spelled word
  • drawback: more words than intended will match the original
  • use-case
    • analyze text when the language is not known
    • handle multiple languages with a single analyzer
    • analyze text when the language combines words in different manner than other European languages
      • japanese: no spaces between words
      • german: long compound words

edge ngrams

  • no user will search for “Database” using the “ase” chunk of characters
    • for many applications, only ngrams that start at the beginning of words are needed
    • that’s where edge n-grams come into play
  • edge n-grams = consecutive prefixes
  • example
    • token: pillar
    • edge n-grams: p, pi, pil, pill, pilla, pillar
  • helpful for searching words with prefix
    • vs prefix query: prefix query is much more time consuming
    • but indexing edge ngrams is longer (and indexes are bigger - contain prefixes)
  • index vs search analyzer
    • different approach than standard - use different analyzers for index and search
      • index time: save all prefixes
      • search time: search for the terms that user typed in
      • good practice to set upper limit
        • for example if search for text with length > 8 - full text search instead of terms
  • prepare index with edge-ngram analyzer
    1.   PUT /index-name
    2.   {
    3.       "settings": {
    4.           "analysis": {
    5.               "filter": {
    6.                   "autocomplete_filter": { // filter that will split tokens into edge ngrams
    7.                       "type": "edge_ngram",
    8.                       "min_gram": 2, // smallest ngrams to generate, default: 1
    9.                       "max_gram": 5 // largest ngrams to generate, default: 2
    10.                   }
    11.               },
    12.               "analyzer": {
    13.                   "autocomplete_analyzer": { // custom analyzer: standard + autocomplete
    14.                       "type": "custom",
    15.                       "tokenizer": "standard",
    16.                       "filter": [ "lowercase", "stop", "autocomplete_filter"]
    17.                   }
    18.               }
    19.           }
    20.       },
    21.       "mappings": {
    22.           "properties": {
    23.               "description": { // field name with autocomplete feature
    24.                   "type": "text", // normal mapping
    25.                   "fields" : { // multi-field mapping
    26.                       "autocomplete": { // mapping responsible for autocomplete feature
    27.                           "type": "text", 
    28.                           "analyzer": "autocomplete_analyzer", 
    29.                           "search_analyzer": "standard" // override - by default, queries use the analyzer defined above
    30.                       },
    31.                       "english": { // other mappings for the same field
    32.                           "type": "text",
    33.                           "analyzer": "english"
    34.                       }
    35.                   }
    36.               }
    37.           }
    38.       }
    39.   }
  • querying for autocomplete
    1.   GET /index-type/_search
    2.   {
    3.       "query": {
    4.           "bool": {
    5.               "should": { // filter, must
    6.                   "match": { "description.autocomplete": "search for descr" }
    7.               }
    8.           }
    9.       }
    10.   }

shingles

  • ngrams at the token level instead of the character level
  • example
    • token: “please divide this sentence into shingles”
    • shingles bigrams: please divide, divide this, this sentence, sentence into, and into shingles
  • used to improve phrase matching, autocomplete, and relevance scoring
    • example: “new york pizza”
      • no distinction between: “new pizza from york” and “york is new to pizza lovers”
      • with bigrams: “new york” is treated as a phrase token
  • rare phrase matches will have a bigger score boost than more common phrases
  • downside: larger indices
    • pre-bake phrase matching
      • build phrases into the index
      • avoid creating phrases at query time and save some processing time/speed
  • index-phrases option on a text field
    • automatically generates and indexes two-term word combinations (shingles) in a hidden subfield
    • allows exact phrase queries (no slop) to run more efficiently, at the expense of a larger index
      • slop = how far we allow the terms to be
  • field type search_as_you_type
    • creates the following fields
      • my_field
        • if an analyzer is not configured, the default analyzer for the index is used
      • my_field._2gram
        • wraps the analyzer of my_field with a shingle token filter of shingle size 2
      • my_field._3gram
        • wraps the analyzer of my_field with a shingle token filter of shingle size 3
      • my_field._index_prefix
        • wraps the analyzer of my_field._3gram with an edge ngram token filter
    • params
      • min_shingle_size
      • max_shingle_size
  • most efficient way to serve a search-as-you-type is multi_match query of type bool_prefix
    • bool_prefix - constructs a bool query from the terms
      • each term except the last is used in a term query
      • last term is used in a prefix query
    • example: please divide this sen
      • is parsed into terms: please, divide, this, sen
      • each term except last is used in exact match
      • last term is used as prefix query: sen -> sentence
  • prepare index with shingles
    1.   PUT /index-type
    2.   {
    3.       "mappings": {
    4.           "properties": {
    5.               "description": { "type": "search_as_you_type"}
    6.               ...
    7.           }
    8.       }
    9.   }
  • querying
    1.   GET /index-type/_search
    2.   {
    3.       "query": {
    4.           "multi_match": {
    5.               "query": "...",
    6.               "type": "bool_prefix",
    7.               "fields": [
    8.                   "description._2gram",
    9.                   "description._3gram"
    10.               ]
    11.           }
    12.       }
    13.   }

stemming

  • process of reducing a word to its root form
    • root form may not be a real word
  • extremely handy when searching
    • match words sharing the root
    • make your searches more flexible than rigid exact matching
  • example
    • word: “administrations”
    • root: “administr”
    • match: “administrator”, “administration”, “administrate”
  • categories
    • algorithmic stemmers
      • based on a set of rules
      • example - remove the -s and -es from the end of plural words
      • advantages
        • little setup
        • little memory
        • typically faster than dictionary stemmers
      • disadvantages
        • problem with irregular words
          • be, are, and am
          • mouse and mice
          • foot and feet
      • types
        • stemmer - porter stemming algorithm, several languages
        • kstem - algorithmic stemming + built-in dictionary
        • porter_stem - porter stemming algorithm, recommended for English
        • snowball - Snowball-based stemming rules, several languages
        • differences in how aggressive they stem
          • more aggressive = chop off more
    • dictionary stemmers
      • stem words by looking in a dictionary
      • advantages
        • more accurate
        • irregular words
        • distinguishes similar (in context of spelling) words but not related conceptually
          • example: organ and organization, broker and broken
      • disadvantages
        • stemmer is only as good as its dictionary
          • must include a significant number of words, be updated regularly, change with language trends
        • use a significant amount of RAM
          • can slow the stemming process significantly
      • types
        • hunspell

fuzzy

  • some typos cannot be solved with n-grams
  • Levenshtein distance between two words
    • minimum number of single-character edits (insertions, deletions or substitutions) required to change
      one word into the other
  • Damerau-Levenshtein distance = Levenshtein + transposition
    • changing a character (box -> fox)
    • removing a character (black -> lack)
    • inserting a character (sic -> sick)
    • transposing two adjacent characters (act -> cat)
  • Levenshtein vs Damerau-Levenshtein
    • compare ‘aex’ and ‘axe’
    • Levenshtein distance: two edits away
      • ‘aex’ is as far from ‘axe’ as ‘faxes’
    • Damerau-Levenshtein: one edit away
      • makes greater intuitive sense in most cases
  • fuzzy query
    1.   GET index-search/_search
    2.   {
    3.       "query": {
    4.           "bool": {
    5.               "should": [
    6.                   { "prefix": { "field-name": "..." } },
    7.                   { "fuzzy": { "field-name": { "value": "...", "fuzziness": 2 } } }
    8.               ]
    9.           }
    10.       }
    11.   }
    • returns documents that contain terms similar (LD distance) to the search term
    • creates a set of all possible variations of the search term within a specified edit distance
    • does not analyze the query text first
      • exact matches for each expansion
    • parameters worth mentioning
      • fuzziness - maximum edit distance allowed for matching
      • max_expansions - maximum number of variations created, defaults: 50
      • prefix_length - number of beginning characters left unchanged when creating expansions, defaults: 0
    • often combined with prefix search
  • stemming context
    • snowball analyzer
    • fuzzy search for ‘running’, will be stemmed to ‘run’
    • misspelled ‘runninga’ stems to ‘runninga’
    • ‘running’ will not match the ‘runninga’
      • ‘run’ is more than 2 edits away from ‘runninga’
    • can cause a bit of confusion
      • use the simple analyzer with fuzzy queries
      • disable synonyms as well

suggesters

  • suggests documents containing similar looking terms
  • still under development
  • types
    • term-suggester
      • suggests terms based on edit distance
    • completion-suggester
      • provides auto-complete/search-as-you-type functionality
      • not meant for spell correction or did-you-mean functionality
      • uses data structures that enable fast lookups, but are costly to build and are stored in-memory
      • supports fuzzy queries
  • define index
    1.   PUT index-name
    2.   {
    3.       "mappings": {
    4.           "properties": {
    5.               "search_associations": {
    6.                   "type": "completion"
    7.               },
    8.               ...
    9.           }
    10.       }
    11.   }
  • index document
    1.   POST index-name/_doc
    2.   {
    3.       "search_associations": [ ... ],
    4.   }
  • query
    1.   POST index-name/_search
    2.   {
    3.       "suggest": {
    4.           "suggest-name": {
    5.               "prefix": "...",
    6.               "completion": {
    7.                   "field": "search_associations"
    8.               }
    9.           }
    10.       }
    11.   }