Trigram search

Trigram search is a method of searching for text when the exact syntax or spelling of the target object is not precisely known[1] or when queries may be regular expressions.[2] It finds objects which match the maximum number of three consecutive character strings (i.e. trigrams) in the entered search terms, which are generally near matches.[3] Two strings with many shared trigrams can be expected to be very similar.[4] Trigrams also allow for efficiently creating search engine indexes for searches that are regular expressions or match the text inexactly. Indexes can significantly accelerate searches.[5][6] A threshold for number of trigram matches can be specified as a cutoff point, after a result is unmatched.[4]

Using trigrams for accelerating searches is a technique used in some systems for code searching, in situations in which queries that are regular expressions may be useful,[5][2][7] in search engines such as Elasticsearch,[8] as well as in databases such as PostgreSQL.[4]

Examples

Consider the string "alice". The trigrams of the string would be "ali", "lic", and "ice", not including spaces.[5] Searching for this string in a database with a trigram-based index would involve finding which objects contain as many of the three trigrams as possible.

As a concrete example of using trigram search to search for a regular expression query, consider searching for the string ab[cd]e, where the brackets denote that the third character in the string being searched for could be c or d. In this situation, one could query the index for objects that have the two trigrams abc and bce or the two trigrams abd and bde. Thus, finding this query would involve no string matching, and could just query the index directly, which can be faster in practice.[2]

See also

References

  1. ^ Hardarson, Omar (1997). "Interactive coding of economic activity using trigram search in BLAISE III" (PDF). International Blaise User Group. Note: This article discusses trigram search as a way of efficiently encoding certain kinds of economic data, and finds that this technique is particularly useful when the users of the system have little context for the structure of the data.
  2. ^ a b c Cox, Russ (January 2012). "Regular Expression Matching with a Trigram Index or How Google Code Search Worked".
  3. ^ Adams, Elizabeth; Meltzer, Arnold (1 March 1993). "Trigrams as index element in full text retrieval: Observations and experimental results". Proceedings of the 1993 ACM conference on Computer science - CSC '93. pp. 433–439. doi:10.1145/170791.170891. ISBN 0897915585. S2CID 16701550.
  4. ^ a b c "F.33. pg_trgm". PostgreSQL Documentation. 2022-05-12. Retrieved 2022-05-28.
  5. ^ a b c "Fast Search Using PostgreSQL Trigram Text Indexes". GitLab. 2016-03-18. Retrieved 2022-05-28.
  6. ^ Zobel, Justin; Moffat, Alistair; Sacks-Davis, Ron (1993). "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" (PDF). Conference on Very Large Databases (VLDB). Note: This research paper does not use the term "trigram search" but does seem to be the first instance in the literature of using n-grams as indices, and is cited in the Russ Cox article as the first instance of the structure of a reverse index based on trigrams. The paper also cited successful performance results from using this style of search.
  7. ^ "Big Grep". resources.sei.cmu.edu. 11 August 2017. Retrieved 2022-06-12. Also called BigGrep. Uses n-grams (not always 3),
  8. ^ "N-gram tokenizer | Elasticsearch Guide [8.2] | Elastic". www.elastic.co. Retrieved 2022-05-28.

Read other articles:

Contrast agent used during X-rays Barium sulfate suspension3D model of barium sulfateClinical dataAHFS/Drugs.comMultum Consumer InformationRoutes ofadministrationby mouth, rectalATC codeV08BA01 (WHO) IdentifiersCAS Number7727-43-7PubChem CID24414UNII25BB7EKE2EChemical and physical dataFormulaBaSO4Molar mass233.3896 Barium sulfate suspension, often simply called barium, is a contrast agent used during X-rays.[1] Specifically it is used to improve visualization of the gastroin...

 

Berikut daftar kabupaten dan/atau kota di provinsi Papua Selatan; No. Kabupaten/kota Ibu kota Bupati/wali kota Luas wilayah (km²)[1] Jumlah penduduk Distrik Kelurahan/kampung Lambang Peta lokasi 1 Kabupaten Asmat Agats Elisa Kambu 31.983,69 110.105 19 -/221 2 Kabupaten Boven Digoel Tanah Merah Hengky Yaluwo 27.108,00 64.285 20 -/112 3 Kabupaten Mappi Kepi Michael Rooney Gomar (Pj.) 24.118,00 108.295 15 2/162 4 Kabupaten Merauke Merauke Romanus Mbaraka 44.071,00 230.932 20 11/179 Refe...

 

Artikel ini tidak memiliki referensi atau sumber tepercaya sehingga isinya tidak bisa dipastikan. Tolong bantu perbaiki artikel ini dengan menambahkan referensi yang layak. Tulisan tanpa sumber dapat dipertanyakan dan dihapus sewaktu-waktu.Cari sumber: Alternaria brassicae – berita · surat kabar · buku · cendekiawan · JSTOR Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala d...

The FIFA Development Award was an award given out by FIFA in 2008 and 2009 which was designed to exemplify the extraordinary amount of effort and financial support which go into increasing the development of football in those countries which need it most. Winners Year Winner Reason Notes 2008 Palestine In recognition of the Palestinian FA, who accomplished the difficult task of renovating the Faisal Al-Husseini Stadium and thus creating a national stadium for Palestine which met FIFA standard...

 

Wolfgang Pauli Il principio di esclusione di Pauli, o principio di esclusione o principio di Pauli, è un principio della meccanica quantistica secondo cui due fermioni identici non possono occupare simultaneamente lo stesso stato quantico. Fu formulato da Wolfgang Pauli nel 1925. Si applica solo ai fermioni, che formano stati quantici antisimmetrici e hanno spin semi-intero, e che includono protoni, neutroni ed elettroni, le tre particelle che compongono la materia ordinaria. Il principio è...

 

Polish trade organization Polish Society of the Phonographic IndustryThe logo of ZPAVAbbreviationZPAVFormation11 July 1991; 32 years ago (1991-07-11)Region served PolandPresidentAndrzej PuczyńskiWebsitezpav.pl The Polish Society of the Phonographic Industry (Polish: Związek Producentów Audio-Video, ZPAV) is the trade organization that represents the interests of the music industry in Poland, and the Polish chapter of the International Federation of the Phonographic Indust...

People in New Zealand of Chinese ancestry Chinese New Zealanders紐西蘭華人 or 纽西兰华人Total population231,387 (2019) 132,906 (born in mainland China) 5.3% of New Zealand's population[1]Regions with significant populationsAuckland171,309Canterbury21,516Wellington21,192Waikato12,084Otago5,439Manawatū-Whanganui4,638Languages New Zealand English Cantonese Teochew Mandarin Hokkien Hakka Other varieties of Chinese Religion Buddhism Taoism Christianity others Related ethnic grou...

 

Arnoul III, Comte Flandria Arnoul III († 22 Februari 1071) a.k.a Arnoul 'si Naas' merupakan seorang Comte Flandria sebagai penguasa muda pada tahun 1070 dan sampai kematiannya pada tahun 1071. Kehidupan Lahir pada sekitar tahun 1055, Arnoul merupakan putra sulung Baudouin VI dan Richilde, Comtesse Mons dan Hainaut.[1] Pada saat ia meninggal pada tahun 1070, Baudouin VI, menyerahkan Flandria kepada putra sulungnya Arnoul III dan Hainaut kepada putranya yang lain Baudouin dengan keten...

 

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (أكتوبر 2020) أروبا فيالألعاب الأولمبيةالرمزARUاللجنةAruban Olympic Committeeالموقعwww.olympicaruba.com باللغة papالميداليات ذهبية 0 فضي...

Aiud NagyenyedKota Lambang kebesaranNegara RumaniaProvinsiAlba (Fehér)StatusMunisipalitasPemerintahan • Wali kotaMihai Horaţiu JosanLuas • Total142,2 km2 (549 sq mi)Populasi (2002) • Total28.934 • Kepadatan203/km2 (530/sq mi)Zona waktuUTC+2 (EET) • Musim panas (DST)UTC+3 (EEST)Situs webhttp://www.aiud.ro/; http://www.aiudonline.ro/ Aiud (bahasa Hungaria: Nagyenyed, Jerman: Straßburg am Mieresc...

 

  此条目的主題是2016年中国大陆电影《摆渡人》。关于其他同名条目,請見「摆渡人」。 擺渡人See You Tomorrow中国海报基本资料导演张嘉佳监制王家卫彭綺華编剧张嘉佳王家卫原著张嘉佳《从你的全世界路过》主演梁朝偉金城武Angelababy陳奕迅張榕容配乐Nathaniel Mechaly摄影曹郁鲍德熹剪辑胡大为制片商阿里巴巴影业集团澤東電影有限公司片长128分钟产地 中国大陆语言粵�...

 

1981 video game 1981 video gameJawbreakerPublisher(s)On-line SystemsTigervision (2600)Programmer(s)Atari 8-bit, 2600John HarrisApple IIOlaf Lubeck[1]Platform(s)Atari 8-bit, Apple II, Atari 2600, Commodore 64Release1981: Atari 8-bit, Apple1982: 26001983: C64Genre(s)MazeMode(s)Single-player Jawbreaker is a Pac-Man clone programmed by John Harris for the Atari 8-bit family and published by On-Line Systems. Released in 1981[2] before an official version of Pac-Man was available, i...

A primary branch of Mandarin Chinese Southwestern MandarinUpper Yangtze MandarinRegionSichuan, Yunnan, Guangxi, Guizhou, Hubei, Hong Kong, othersNative speakers260 million (2012)[1]Language familySino-Tibetan SiniticChineseMandarinSouthwestern MandarinOfficial statusOfficial language in China (Guangxi)Recognised minoritylanguage in Hong Kong Macau Myanmar (Wa State, Kokang Self-Administered Zone) Vietnam (Lào Cai Province)Language codesISO 639-...

 

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (February 2017) Humanist Counseling in the Dutch Armed Forces is a task in the Armed forces of the Netherlands. Humanist counsellors, sometimes called humanist chaplain, contribute to the (mental) well-being of military personnel, those related to them, and veterans. They do this through visible presence at the workplace, personal conta...

 

River in New South Wales, AustraliaLansdowne RiverLansdowne River at Coopernook, 2023LocationCountryAustraliaStateNew South WalesIBRANSW North CoastDistrictMid North CoastLocal government areaGreater TareePhysical characteristicsSourceMount Gibraltar, Gibraltar Range • locationnear Upper Lansdowne • elevation740 m (2,430 ft) Mouthconfluence with the Manning River • locationnear Coopernook • elevation0 m (0...

American swimmer (born 1958) Lelei FonoimoanaPersonal informationFull nameLelei Alofa MooreNational teamTeam USABorn (1958-11-04) November 4, 1958 (age 65)Sterling, IllinoisHeight5 ft 8 in (1.73 m)Weight143 lb (65 kg)SportSportSwimmingStrokesButterflyClubLakewood Aquatic ClubCollege teamBrigham Young University Cougars Medal record Women's swimming Representing the  United States Olympic Games 1976 Montreal 4x100 m medley relay Lelei Alofa Fonoimoa...

 

Municipio de Becker Municipio Municipio de BeckerUbicación en el condado de Roberts en Dakota del Sur Ubicación de Dakota del Sur en EE. UU.Coordenadas 45°32′10″N 96°49′50″O / 45.5361, -96.8306Entidad Municipio • País  Estados Unidos • Estado  Dakota del Sur • Condado RobertsSuperficie   • Total 77.19 km² • Tierra 73.76 km² • Agua (4.44 %) 3.43 km²Altitud   • Media 346 m s. n. m.Pobl...

 

White MassacreAn 1876 map of northeastern New Mexico with the principal sites plotted.DateOctober 18, 1849LocationNew Mexico Territory vteApache Wars Jicarilla War Point of Rocks Wagon Mound Bell's Fight Cieneguilla Ojo Caliente Canyon Texas–Indian wars Diablo Mountains Antelope Hills Expedition Little Robe Creek 1st Adobe Walls Chiricahua Wars Cooke's Spring Bonneville Expedition Madera Canyon Mimbres River Bascom Affair Tubac Cookes Canyon Florida Mountains Gallinas Mountains Placito Pino...

American former tennis player Larry NaglerNagler in 1960Country (sports)United StatesResidenceLos Angeles, California, USBorn (1940-07-01) July 1, 1940 (age 83)Queens, New York, USCollegeUniversity of California, Los Angeles (UCLA)SinglesGrand Slam singles resultsWimbledon1R (1964)US Open4R (1963)DoublesGrand Slam doubles resultsWimbledon2R (1964) Medal record Maccabiah Games 1977 Israel Men's Doubles 1977 Israel Men's Singles Larry Nagler (born July 1, 1940) is an American former c...

 

Motor vehicle Buick EnvisionOverviewManufacturerBuick (General Motors)Production2014–presentModel years2016–present (North America)AssemblyChina: Yantai (SAIC-GM)Body and chassisClassCompact crossover SUV[1][2]Body style5-door SUVLayoutFront-engine, front-wheel-drive or all-wheel-drive The Buick Envision is a compact crossover SUV manufactured by General Motors and marketed under the Buick brand since 2014. It is exclusively manufactured in China by the SAIC-GM j...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!