{"action":"created","issue":{"url":"https://api.github.com/repos/elastic/elasticsearch/issues/13710","labels_url":"https://api.github.com/repos/elastic/elasticsearch/issues/13710/labels{/name}","comments_url":"https://api.github.com/repos/elastic/elasticsearch/issues/13710/comments","events_url":"https://api.github.com/repos/elastic/elasticsearch/issues/13710/events","html_url":"https://github.com/elastic/elasticsearch/issues/13710","id":107688559,"number":13710,"title":"NGram Tokenizer ignoring search terms smaller than n","user":{"login":"mrdotnic","id":11489835,"avatar_url":"https://avatars.githubusercontent.com/u/11489835?v=3","gravatar_id":"","url":"https://api.github.com/users/mrdotnic","html_url":"https://github.com/mrdotnic","followers_url":"https://api.github.com/users/mrdotnic/followers","following_url":"https://api.github.com/users/mrdotnic/following{/other_user}","gists_url":"https://api.github.com/users/mrdotnic/gists{/gist_id}","starred_url":"https://api.github.com/users/mrdotnic/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mrdotnic/subscriptions","organizations_url":"https://api.github.com/users/mrdotnic/orgs","repos_url":"https://api.github.com/users/mrdotnic/repos","events_url":"https://api.github.com/users/mrdotnic/events{/privacy}","received_events_url":"https://api.github.com/users/mrdotnic/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":6,"created_at":"2015-09-22T10:46:10Z","updated_at":"2016-01-25T13:39:41Z","closed_at":"2015-09-22T13:44:28Z","body":"NGram Tokenizers are a very useful filter to match parts of compound words. Compound words can be commonly found p.e. in the German language, but occur in English as well (p.e. \"thunderstorm\").\r\nhttps://www.elastic.co/guide/en/elasticsearch/guide/current/ngrams-compound-words.html\r\n\r\nNGram (also called n-gram) Tokenizers split up words into token sequences. Each token has a specified minimum gram length (min_gram) and maximum gram length (max_gram). Tokens consisting of three letters p.e. are called trigrams.\r\nUsing trigrams as our starting point, the word \"peanut\" for example would be divided into the three-letter-tokens \"pea\", \"ean\", \"anu\" and \"nut\".\r\nSearching for \"peanut\" would therefore also (partially) match words like \"**pea**ce\", \"S**ean**\", \"**Anu**bis\" and \"**nut**rition\". They all contain one of these tokens, but might not be words (or the document if they are all in one) we want to see as our results.\r\nStatistically speaking we would then be suffering type I errors (false positives).\r\nhttps://en.wikipedia.org/wiki/Type_I_and_type_II_errors\r\n\r\nObviously we might then try longer min_gram lengths, p.e. four or five letters long.\r\nWith five-grams, \"peanut\" would be split up in \"peanu\" and \"eanut\", giving us far more exact results.\r\nOne might come to the conclusion, the longer the n-gram, the better.\r\nThough this is be true to some extent and for some purposes, we will run into another problem.\r\n\r\nElasticsearch's NGram Tokenizers ignore search terms with a length smaller than the specified min_gram!\r\nThat means the actual search term will often be significantly shorter and more vague than intended. If there will be a search term left at all.\r\n\r\nWe might p.e. search for \"step by step\", trying to find backpacks of this company. Here we have multiple query strings, combined by the AND operator.\r\nIf we use our five-gram Tokenizer every word will be ignored. We will have no results resulting in type II errors (false negatives).\r\nBigrams would respect every word, but lead to a lot of type I errors (see above the \"peanut\" example).\r\nTrigrams would only exclude the word \"by\" and respect the rest while being more accurate. But trigrams match the unwanted \"Steckdosenleiste\" (= multi-outlet power strip). **\"Ste\"**, \"tep\", **\"Ste\"**, \"tep\" on the one hand and **\"ste\"**, \"tec\", \"eck\", \"ckd\", \"kdo\", \"dos\", \"ose\", \"sen\", \"enl\", \"nle\", \"lei\", \"eis\", \"ist\", **\"ste\"** on the other means 50% of the search terms are matched!\r\nSo we would might opt for a four-gram Tokenizer, bringing us good results this time.\r\nBut then searching for \"Jay Smith\" would also give us somebody called \"John Smith\" with the same exact match percentage (type I error).\r\n\r\nEven if we wouldn't care for words smaller than four letters, sure enough one can come up with an example where five-grams would be needed.\r\nSearching for \"Recht\" (= law), a four-gram Tokenizer will match \"Echt + rechnung\" (= calculation/bill + real):\r\n\"Recht\" splits up into **\"rech\"**, **\"echt\"** while \"Echt + rechnung\" splits up into **\"echt\"** and **\"rech\"**, \"echn\", \"chnu\", \"hnun\", \"nung\", presenting a perfect match. This might come as a surprise, as those words are in two differents fields (the fields \"name\" and \"description\"), making a good example of how unintended and undesired a match can be.\r\nRespecting the token order (\"Rech\" before \"echt\") of our search term would help here, but is not supported. Same goes for the \"step by step\" example.\r\n\r\nIf it were possible for the Elasticsearch NGram Tokenizer to fall back to smaller sized n-grams, using five-grams for \"Smith\" and trigrams for \"Jay\" (instead of ignoring \"Jay completely), our problems described above would be gone. We would have relative n-gram precision according to the length of our search terms. But as it stands, we are forced to choose between lots of type I or lots of type II errors.\r\n\r\nTo sum the examples we have the following situation:\r\n1. A gram size smaller than five leads to problems with our search term \"Recht\" (type I errors).\r\n2. A gram size larger than three ignores \"jay\" in \"jay smith\" (type I error).\r\n3. A gram size larger than four ignores \"step by step\" (type II error).\r\n\r\nThis is why a combination of three to five grams (p.e. min_gram=3 and max_gram=5) also fails.\r\n\r\n\r\nFeel free to play around with the examples in my gist: https://www.found.no/play/gist/6d27486e51bdda88dd84\r\nEdit the min_gram and max_gram sizes to your liking in the \"Analysis\" section (center left), rerun the queries (\"Run\" in the top right) and see the altered \"Results\" section (bottom right) with our Searches # 1, # 2 and # 3.\r\nSearching for \"jay smith\" corresponds to Search # 1, searching for \"step by step\" to Search # 2 and finally searching for \"recht\" to Search # 3. To try out other search terms, edit the queries in the \"Searches\" section (top right).\r\nOr edit the \"Documents\" section (top left), to experiment with different words to be searched for.\r\n\r\n\r\nTo summarize: \r\nIf we want to match search terms to compound words (\"thunderstorm\"), NGram Tokenizers are a fine tool. They split up words into tokens of a predefined size. \r\nBut Elasticsearch's fixed size NGram Tokenizers force us to choose between either lots of type I or type II errors. What works well for short words like \"Jay\" won't work for longer words like \"Recht\" (German for law) and vice versa.\r\nDesired would be a flexible NGram Tokenizer. This means being able to switch from longer NGram Tokenizers (p.e. five-grams) to shorter (p.e. trigrams), as the search terms become shorter. Another, maybe more complicated way could be to make the NGram Tokenizer respect the order of the tokens."},"comment":{"url":"https://api.github.com/repos/elastic/elasticsearch/issues/comments/174512170","html_url":"https://github.com/elastic/elasticsearch/issues/13710#issuecomment-174512170","issue_url":"https://api.github.com/repos/elastic/elasticsearch/issues/13710","id":174512170,"user":{"login":"felixbarny","id":2163464,"avatar_url":"https://avatars.githubusercontent.com/u/2163464?v=3","gravatar_id":"","url":"https://api.github.com/users/felixbarny","html_url":"https://github.com/felixbarny","followers_url":"https://api.github.com/users/felixbarny/followers","following_url":"https://api.github.com/users/felixbarny/following{/other_user}","gists_url":"https://api.github.com/users/felixbarny/gists{/gist_id}","starred_url":"https://api.github.com/users/felixbarny/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/felixbarny/subscriptions","organizations_url":"https://api.github.com/users/felixbarny/orgs","repos_url":"https://api.github.com/users/felixbarny/repos","events_url":"https://api.github.com/users/felixbarny/events{/privacy}","received_events_url":"https://api.github.com/users/felixbarny/received_events","type":"User","site_admin":false},"created_at":"2016-01-25T13:39:41Z","updated_at":"2016-01-25T13:39:41Z","body":"Am I doing something wrong or is that a use case that can't be handled with Elasticsearch? Any chance you can reopen this issue until it gets resolved?\r\n\r\nThanks a lot :)"}}