Skompresowane drzewo trie

Skompresowane drzewo trie (również: drzewo Patricia, drzewo pozycyjne) – struktura danych przechowująca zbiór ciągów.

Przykładowe skompresowane drzewo trie

Koncepcja

Skompresowane drzewo trie jest wariantem drzewa trie, w którym krawędzie mogą być etykietowane ciągami znaków, a nie tylko pojedynczymi znakami. Kompresja drzewa trie polega na „ściągnięciu” nierozgałęzionych ścieżek i oznaczeniu nowych krawędzi słowami złożonymi z liter na pierwotnych krawędziach. W rezultacie każdy węzeł wewnętrzny ma co najmniej dwóch synów.

Skompresowane drzewo trie może przechowywać łańcuchy znaków, ciągi bitów stanowiące zapis liczb naturalnych lub adresów IP lub też ciągi dowolnych elementów z porządkiem leksykograficznym.

Operacje

Poniższe operacje na skompresowanym drzewie trie przechowującym zbiór słów są wykonywane w czasie

  • wyszukiwanie – informuje czy dane słowo należy do zbioru. Realizowane jak w drzewie trie, ale przejście niektórych krawędzi może oznaczać dopasowanie wielu znaków.
  • wstawienie słowa – przeszukujemy drzewo, dopóki nie możemy zejść niżej. W tym momencie albo tworzymy nową krawędź z etykietą równą pozostałemu sufiksowi słowa, albo – jeżeli istnieje krawędź, która ma wspólny z tym sufiksem prefiks, rozbijamy tę krawędź na dwie krawędzie (z których pierwsza jest etykietowana tym wspólnym prefiksem, a druga pozostałą częścią pierwotnej etykiety), a następnie do nowego wierzchołka dołączamy krawędź z pozostałą częścią wstawianego słowa.
  • usuwanie słowa – usuwamy odpowiedni liść. Jeżeli jego ojciec ma tylko jednego syna, wycinamy go, łącząc etykiety sąsiadujących z nim krawędzi.
  • znajdowanie poprzednika i następnika danego słowa w porządku leksykograficznym.

Zastosowania

Skompresowane drzewa trie znajdują zastosowanie w konstrukcji tablic asocjacyjnych z ciągami jako kluczami. Szczególne znaczenie mają w dziedzinie trasowania IP. Szczególne drzewa Patricia, drzewa sufiksowe, są stosowane w algorytmach tekstowych.

Historia

Drzewa Patricia po raz pierwszy wprowadził Donald R. Morrison w 1968. Nazwa drzewa pochodzi od skrótu PATRICIA: Practical Algorithm To Retrieve Information Coded in Alphanumeric (Praktyczny algorytm wyszukiwania informacji zakodowanych w formie alfanumerycznej)[1].

Zobacz też

Przypisy

  1. ↑ Informacje o publikacji Donalda R. Morrisona w archiwum ACM [1].

Read other articles:

Jacqui Smith

Jacqui Smith Jacqueline Jill Smith (lahir 3 November 1962) adalah seorang penyiar, komentator politik dan mantan politikus Partai Buruh Britania Raya. Ia merupakan anggota parlemen dari 1997 sampai 2010, Menteri Dalam Negeri perempuan pertama dan wanita ketiga yang memegang salah satu jabatan pemerintahan besar di Inggris, setelah Margaret Thatcher (Perdana Menteri) dan Margaret Beckett (Menteri Luar Negeri). Pranala luar Jacqui Smith MP – official website. Labour Party. Diarsipkan dari ver...

 

Referendum pemerintahan sendiri Greenland 1979

Greenland Artikel ini adalah bagian dari seri Politik dan KetatanegaraanGreenland Konstitusi Konstitusi Undang-Undang Suksesi Kebebasan berbicara dan pers Perpajakan Monarki Penguasa Monarki Ratu Margrethe II Pangeran Mahkota Frederik Keluarga Kerajaan Dewan Pribadi Purveyors to the Royal Court Wilayah Kerajaan  Kerajaan Denmark  Greenland  Denmark  Kepulauan Faroe EksekutifRegeringen Pemerintah Kerajaan Denmark Komisaris Tinggi (daftar) Mikaela Engell Naalakkersuisut Peme...

 

Ekonomi Keselamatan

Tritunggal Kudus, Jan Cornelisz Vermeyen, abad ke-16 Ekonomi Keselamatan, yang juga disebut Ekonomi Ilahi, adalah bagian dari wahyu ilahi dalam tradisi Kristen yang menyinggung soal kisah Allah menciptakan dan mengurus dunia, terutama rencana keselamatan-Nya melalui Gereja. Dari kata Yunani oikonomia (ekonomi), yang artinya, kepengurusan rumah tangga.[1] Ini adalah unsur dan sumber daya yang diwahyukan oleh Allah sebagai kebutuhan untuk keselamatan melalui wahyu khusus, kitab suci Per...

Canada Games

Biennial Canadian sporting event, alternating between winter and summer sports See also: List of Canada Games Canada GamesJeux du CanadaOpening ceremonies2017 Canada Summer GamesStatusActiveGenreMulti-sport eventFrequencyBiannualLocation(s)VariousCountryCanadaInauguratedWinter Games1967; 57 years ago (1967)Summer Games1969; 55 years ago (1969)Organised byCanada Games CouncilWebsitecanadagames.ca The Canada Games (French: Jeux du Canada) is a multi-sport eve...

 

The Bacchae (film)

American filmThe BacchaeDionysus (Richard Werner) in The Bacchae, directed by Brad Mays, 2000.Directed byBrad MaysWritten byBrad Mays, adapted from EuripidesProduced byLorenda Starfelt, John MorrisseyStarringRichard Werner, Jonathan Klein, Lynn Odell, William Dennis Hunt, Will Shepherd, Ramona Reeves, Elyse Ashton, Kiersten MorganCinematographyJacob PingerEdited byBrad MaysMusic byPeter GirardRunning time88 minutesCountryUnited StatesLanguageEnglish The Bacchae is an independent film adaptati...

 

Wedding Dress (film)

Wedding DressTheatrical posterNama lainHangul웨딩드레스 Alih Aksara yang DisempurnakanWeding deureseuMcCune–ReischauerWeting dŭresŭ SutradaraKwon Hyung-jinProduserChoi Sun-joong Choi Pyeong-ho Na Gyeong-chanDitulis olehYoo Young-ahPemeranSong Yun-ah Kim Hyang-giPenata musikMok Young-jinSinematograferBaek Dong-hyeonPenyuntingPark Gok-ji Jeong Jin-huiPerusahaanproduksiRoad PicturesDistributorSidus FNHTanggal rilis 14 Januari 2010 (2010-01-14) Durasi109 menitNegaraKorea...

Discovery doctrine

Concept of public international law This article is about the discovery of land under public international law. For pre-trial phase of a lawsuit, see Discovery (law). Property law Part of the common law series Types Personal property Community property Real property Unowned property Acquisition Gift Adverse possession Deed Conquest Discovery Accession Lost, mislaid, and abandoned property Treasure trove Bailment License Alienation Estates in land Allodial title Fee simple Fee tail Life estate...

 

Oxymorphone

Opioid analgesic drug Not to be confused with Oxymorphazone. OxymorphoneClinical dataTrade namesNumorphan, Numorphone, Opana, othersOther names14-HydroxydihydromorphinoneAHFS/Drugs.comMonographMedlinePlusa610022License data US DailyMed: Oxymorphone DependenceliabilityHighAddictionliabilityHighRoutes ofadministrationBy mouth, buccal, sublingual, intranasal, intravenous, epidural, subcutaneous, intramuscularDrug classOpioidATC codeN02AA11 (WHO) Legal statusLegal status AU:&#...

 

Mack Mattingly

American politician (born 1931) This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Mack Mattingly – news · newspapers · books · scholar · JSTOR (September 2010) (Learn how and when to remove this t...

Henri Ier de Germanie

Pour les articles homonymes, voir Henri et Henri Ier. Henri Ier de Germanie Portrait imaginaire d'Henri Ier de Germanie par Ottokar Walter (1904). Titre Duc de Saxe 912 – 936(24 ans) Prédécesseur Otton Ier de Saxe Successeur Otton Ier du Saint-Empire Roi de Francie Orientale 919 – 936(17 ans) Prédécesseur Conrad Ier de Germanie Successeur Otton Ier du Saint-Empire Biographie Dynastie Ottoniens Date de naissance 876 Lieu de naissance Memleb...

 

Pecos Bill

Fictional cowboy This article is about the fictional character. For the restaurant, see Pecos Bill Tall Tale Inn and Cafe. For other uses, see Pecos Bill (disambiguation). Fictional character Pecos BillOn one of his various adventures, Bill managed to lasso a tornado using a snakeFirst appearanceSaga of Pecos Bill (1917)Created byEdward S. O'ReillyBirthplaceTexasIn-universe informationFull namePecos BillSpeciesHumanGenderMaleOccupationCowboySignificant otherSlue-Foot SueNationalityAmerican Pe...

 

Ираклеониты

Ираклеониты — ученики гностика Ираклеона (II век). Упоминаются как особая секта Епифанием и Августином; при крещении и миропомазании они соблюдали обряд помазания елеем и при этом произносили воззвания на арамейском языке, которые должны были освободить душу от власт�...

SoCal Lashings

Los Angeles-based Professional Cricket Organization SoCal LashingsLeagueMinor League CricketConferenceWestern Division (Pacific Conference)PersonnelCaptainDale PhillipsOwnerAbhimanyu RajpDeepak GosainTeam informationCityLos Angeles, California, USAColours  Purple, and   Gold.Founded2020; 4 years ago (2020)Home groundLeo Magnus Cricket ComplexCapacity5,000 The SoCal Lashings, also known as the Los Angeles Lashings, are an American professional Twenty20 franchise cri...

 

2020年夏季奧林匹克運動會奧地利代表團

2020年夏季奥林匹克运动会奥地利代表團奥地利国旗IOC編碼AUTNOC奧地利奧林匹克委員會網站www.olympia.at（德文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員75參賽項目21个大项旗手开幕式：托马斯·扎亚克（英语：Thomas Zajac）和塔尼娅·弗兰克（帆船）[1]闭幕式：安德烈亚斯·米勒（自行车）[2]...

 

LSU Health Sciences Center New Orleans

Medical center LSU Health Sciences Center New OrleansTypePublic universityEstablished1931ChancellorLarry H. Hollier, MD, FACS, FACC, FRCS (Eng.)Academic staff649Students2,699LocationNew Orleans, Louisiana, United States]CampusUrbanAffiliationsLSU SystemWebsitewww.lsuhsc.edu The Louisiana State University Health Sciences Center New Orleans is a public university focused on the health sciences and located in New Orleans, Louisiana. It is part of the LSU System and is the home of six schools (in...

哈萨克斯坦总统

此条目序言章节没有充分总结全文内容要点。 (2019年3月21日)请考虑扩充序言，清晰概述条目所有重點。请在条目的讨论页讨论此问题。 哈萨克斯坦總統哈薩克總統旗現任Қасым-Жомарт Кемелұлы Тоқаев卡瑟姆若马尔特·托卡耶夫自2019年3月20日在任任期7年首任努尔苏丹·纳扎尔巴耶夫设立1990年4月24日（哈薩克蘇維埃社會主義共和國總統） 哈萨克斯坦 哈萨克斯坦政府...

 

Scottish Cup

Association football competition in Scotland For other uses, see Scottish Cup (disambiguation). Football tournamentScottish CupFounded1873; 151 years ago (1873)RegionScotlandEngland (1 team)Number of teams131 (2023–24)Qualifier forUEFA Europa LeagueCurrent championsCeltic(42nd title)Most successful club(s)Celtic(42 titles)Websitescottishfa.co.uk 2023–24 Scottish Cup The Scottish Football Association Challenge Cup,[1] commonly known as the Scottish Cup&#...

 

National Electrical Code

Electrical wiring standard Electrical installations Wiring practice by region or country North American practice United Kingdom practice Regulation of electrical installations BS 7671 UK wiring regulations IEC 60364 IEC international standard Canadian Electrical Code (CE Code) U.S. National Electrical Code (NEC) Cabling and accessories AC power plugs and sockets Cable tray Electrical conduit Mineral-insulated copper-clad cable Multiway switching Steel wire armoured cable Ring main unit Ring c...

Johannes Giesberts

Cet article est une ébauche concernant un homme politique prussien. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Johannes Giesberts Johannes Giesberts (2e en partant de la gauche) au sein de la délégation allemande présente à Versailles pour la signature du traité, en 1919. Fonctions Ministre du Reich aux Postes 13 février 1919 – 14 novembre 1922(3 ans, 9 mois et 1 jour) Chancelier Phi...

 

1870 في فنلندا

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) 1870 في فنلندامعلومات عامةجانب من جوانب فنلندا تصنيف:1871 في فنلندا تعديل - تعديل مصدري - تعديل ويكي بيانات سن...