Префіксний код

Префіксний код в теорії кодування — код зі словом змінної довжини, що має таку властивість (виконання умови Фано): якщо в код входить слово a, то для будь-якого непорожнього рядка b слова ab в коді не існує. Хоча префіксний код складається зі слів різної довжини, ці слова можна записувати без розділового символу.

Наприклад, код, що складається з слів 0, 10 і 11, є префіксним, і повідомлення 01001101110 можна розбити на слова єдиним чином: 

0 10 0 11 0 11 10

Код, що складається з слів 0, 10, 11 і 100, префіксним не є, і те саме повідомлення можна трактувати декількома способами. 

0 10 0 11 0 11 10 
0 100 11 0 11 10

Визначення

Так звані «префікси» можуть бути отримані шляхом послідовного відкидання останнього знаку кодової комбінації. Наприклад, для кодової комбінації 11101101 префіксами будуть 11101101, 1110110, 111011, 11101, 1110, 111, 11, 1.

Якщо проміжків чи інших знаків пунктуації між кодовими комбінаціями немає, то для однозначного декодування комбінації 111011101 жодна з кодових комбінацій не може бути представлена перерахованими варіантами (префіксами). Код називається префіксним, якщо жодна з його комбінацій не є префіксом іншої комбінації того ж коду. Частина кодової комбінації, яка доповнює префікс до самої комбінації, називається суфіксом. Префіксні коди наочно можуть бути представлені за допомогою кодових дерев. Якщо ні один вузол кодового дерева не є вершиною даного коду, то він має властивості префікса. Вузли дерева, які не з'єднуються з іншими, називаються кінцевими. Комбінації, які їм відповідають, є кодовими комбінаціями префіксного коду.

Приклади

Будь-який код зі словом фіксованої довжини, очевидно, є префіксним. Розглянемо декілька нетривіальних прикладів.

Код Морзе не є префіксним. У нього, крім крапки і тире, входить також символ-розділювач — пауза довжиною з тире.

Див. також


Інформаційні технології Це незавершена стаття про інформаційні технології.
Ви можете допомогти проєкту, виправивши або дописавши її.

Read other articles:

Advance Arc Harmony

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada September 2020. Advance Arc HarmonyAsal JepangGenreJ-POPTahun aktif14 November 2018 -LabelTokuma JapanSitus webhttp://advance-arc-harmony.tokyo/Advance Arc Harmony, yang berjudul Admoni (アドモニ), adalah sebuah grup idola Jepang yang dibentuk pada November...

 

 

Talumopatu, Tapa, Bone Bolango

Desa TalumopatuDesaNegara IndonesiaProvinsiGorontaloKabupatenBone BolangoKecamatanTapaKode pos96582Kode Kemendagri75.03.01.2004 Luas123 haJumlah penduduk1926Kepadatan- Kantor Desa Talumopatu, Kec. Tapa Untuk desa di Kabupaten Gorontalo, lihat Talumopatu, Mootilango, Gorontalo. Talumopatu adalah salah satu desa di Kecamatan Tapa, Kabupaten Bone Bolango, Gorontalo, Indonesia. Pranala luar (Indonesia) Keputusan Menteri Dalam Negeri Nomor 050-145 Tahun 2022 tentang Pemberian dan Pemutakhiran...

 

 

羅生門 (電影)

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要补充更多来源。 (2018年3月17日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：羅生門 (電影) — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 �...

Laptev Sea

Marginal sea in the Arctic Ocean north of Siberia between the Kara Sea and the East Siberian Sea Laptev SeaLaptev SeaCoordinates76°16′7″N 125°38′23″E / 76.26861°N 125.63972°E / 76.26861; 125.63972TypeSeaBasin countriesRussiaSurface area700,000 km2 (270,000 sq mi)Average depth578 m (1,896 ft)Max. depth3,385 m (11,106 ft)Water volume403,000 km3 (3.27×1011 acre⋅ft)References[1][2][3] ...

 

 

Rutgers Scarlet Knights wrestling

Wrestling team of Rutgers University Rutgers Scarlet KnightsUniversityRutgers University-New BrunswickHead CoachScott Goodale (17th season)ConferenceBig TenLocationNew Brunswick, NJArenaRutgers Athletic Center (RAC)(Capacity: 8,000)NicknameScarlet KnightsColorsScarlet[1]  The Rutgers Scarlet Knights wrestling team represents Rutgers University of New Brunswick, New Jersey. The squad is coached by Scott Goodale, who is a 1995 graduate of Lock Haven University. He came to Rutgers f...

 

 

دوري جزر فارو الممتاز 2012

دوري جزر فارو الممتاز 2012 تفاصيل الموسم دوري جزر فارو الممتاز  النسخة 70  البلد جزر فارو  التاريخ بداية:24 مارس 2012  نهاية:6 أكتوبر 2012  المنظم اتحاد جزر فارو لكرة القدم  البطل ستريمور  مباريات ملعوبة 135   عدد المشاركين 10   دوري جزر فارو الممتاز 2011  دوري جز�...

Adi Sarana Armada

PT Adi Sarana Armada TbkNama dagangAssaSebelumnyaPT Quantum Megahtama Motor (1999-2003)PT Adira Sarana Armada (2003-2009)JenisPerseroan terbatasKode emitenIDX: ASSAIndustriTransportasiDidirikan17 Desember 1999; 24 tahun lalu (1999-12-17)KantorpusatJakarta, IndonesiaWilayah operasiIndonesiaTokohkunciProdjo Sunarjanto Sekar Pantjawati[1](Direktur Utama)Erida[1](Komisaris Utama)MerekAssa RentAssa LogisticsAssa Driver ServicesJBA BidWin AuctionShare CarCaroline.idAnterajaJasa...

 

 

FK Željezničar Sarajevo

ŽeljezničarZeljeznicar's emblemNama lengkapFudbalski Klub Željezničar SarajevoJulukanŽeljoPlavi (Blues)Berdiri19 September 1921; 102 tahun lalu (1921-09-19)StadionGrbavica Stadium(Kapasitas: 16,100[1])KetuaAlmir GredićManajerAmar OsimLigaPremier League2020/21ke-7Situs webSitus web resmi klub Kostum kandang Kostum tandang Musim ini FK Željezničar Sarajevo merupakan sebuah klub sepak bola Bosnia-Herzegovina yang bermain di divisi utama Liga Utama Bosnia-Herzegovina. Di...

 

 

Nasaruddin Umar

Nasaruddin Umar Imam Besar Masjid Istiqlal ke-5PetahanaMulai menjabat 22 Januari 2016PendahuluProf. Dr. KH. Ali Mustafa Yaqub, MAPenggantiPetahanaWakil Menteri Agama Indonesia ke-1Masa jabatan2011–2014PresidenSusilo Bambang YudhoyonoWakil PresidenBoedionoPendahuluTidak ada; jabatan baruPenggantiZainut Tauhid Sa'adi Informasi pribadiLahir23 Juni 1959 (umur 64)Ujung, Dua Boccoe, Bone, IndonesiaAlma materUIN Alauddin MakassarUIN Syarif Hidayatullah JakartaMc Gill University Ka...

Ilyushin Il-1

Ilyushin Il-1 (Cyrillic Ильюшин Ил-1) adalah pesawat tempur Soviet dikembangkan selama Perang Dunia II oleh biro desain Ilyushin. Ia dirancang pada tahun 1943 sebagai pesawat tempur lapis baja untuk digunakan pada ketinggian rendah dan menengah terhadap pesawat tempur Jerman terbaru, tetapi pada saat itu melakukan penerbangan pertama pada tahun 1944, Soviet telah mencapai superioritas udara dan karena itu tidak dibutuhkan. Hanya satu contoh dibangun, tetapi versi serangan dua kursi p...

 

 

Bill Hayden

Australian politician (1933–2023) For the fictional spy character, see Bill Haydon. William Hayden redirects here. For the Adjutant General of the State of Connecticut, see William Hayden (soldier). The HonourableBill HaydenACHayden in 197321st Governor-General of AustraliaIn office16 February 1989 – 16 February 1996MonarchElizabeth IIPrime MinisterBob Hawke Paul KeatingPreceded bySir Ninian StephenSucceeded bySir William DeaneLeader of the OppositionIn office22 December 1977...

 

 

The Hundred (cricket)

British 100-ball cricket competition The Hundred redirects here. For other uses, see Hundred (disambiguation) and The 100 (disambiguation). The HundredCountries England Wales AdministratorEngland and Wales Cricket BoardFormat100-ball cricketFirst edition2021Latest edition2023Next edition2024Tournament formatRound-robin league and PlayoffsNumber of teams8 (women's)8 (men's)Current championWomen: Southern Brave (1st title)Men: Oval Invincibles (1st title)Most successfulWomen: Oval Invincibles (...

Fish sauce

Condiment made from fish Fish sauceTypeCondimentPlace of originVarious placesRegion or stateSoutheast Asia and East AsiaAssociated cuisineMyanmar, Cambodia, China, Laos, Philippines, Thailand, and VietnamMain ingredientsFish, salt  Media: Fish sauce Part of a series onChinese cuisine Regional cuisines Four Great Traditions Chuan (Sichuan) Lu (Shandong) Yue (Guangdong) Huaiyang (Jiangsu) Eight Great Traditions(+all above) Anhui Fujian Hunan Zhejiang Ten Great Traditions(+all above) Be...

 

 

Fort Wayne Pistons 1954-1955

Fort Wayne PistonsStagione 1954-1955Sport pallacanestro Squadra Detroit Pistons AllenatoreCharley Eckman NBA43-29 (.597)Division: 1º posto (Western) PlayoffFinale (perso 3-4 contro Syracuse) StadioWar Memorial Coliseum 1953-1954 1955-1956 La stagione 1954-55 dei Fort Wayne Pistons fu la 6ª nella NBA per la franchigia. I Fort Wayne Pistons vinsero la Western Division con un record di 43-29. Nei play-off vinsero la finale di division con i Minneapolis Lakers (3-1), perdendo poi la finale...

 

 

Новотитаровское сельское поселение

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

Elizabeth the Queen (play)

1930 Broadway three-act play written in blank verse by Maxwell Anderson Elizabeth the QueenFirst edition 1930Written byMaxwell AndersonDate premieredNovember 27, 1930Place premieredGuild TheatreNew York CityOriginal languageEnglishGenreDramaSettingvarious parts of Whitehall palace Elizabeth the Queen was a 1930 Broadway three-act play written in blank verse by Maxwell Anderson, produced by the Theatre Guild, directed by Philip Moeller and with scenic and costume design by Lee Simonson. It ran...

 

 

John Cho

American actor (born 1972) John ChoCho in June 2018BornCho Yo-Han (1972-06-16) June 16, 1972 (age 51)Seoul, South KoreaNationalityAmericanEducationUniversity of California, Berkeley (BA)OccupationActorYears active1997–presentSpouse Kerri Higuchi ​(m. 2006)​Children2Korean nameHangul조요한Revised RomanizationJo Yo(-)hanMcCune–ReischauerCho Yohan John Cho (born Cho Yo-Han; June 16, 1972)[1] is an American actor known for his roles as Harold ...

 

 

Ann Lambton

British historian For the British actress, see Anne Lambton. Ann LambtonBornAnn Katharine Swynford Lambton(1912-02-08)8 February 1912Newmarket, SuffolkDied19 July 2008(2008-07-19) (aged 96)Wooler, NorthumberlandNationalityBritishAlma materSOAS University of LondonOccupationHistorian Ann Katharine Swynford Lambton, OBE, FBA (8 February 1912 – 19 July 2008), usually known as A.K.S. Lambton or Nancy Lambton,[1] was a British historian and expert on medieval and early ...

University of the West

Buddhist private university in Rosemead, California This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: University of the West – news · newspapers · books · scholar · JSTOR (January 2010) (Learn how and when to remove this message) University of the West西來大學 (Chinese)MottoAwaken Your PurposeTypePriv...

 

 

UEFA Women's Euro 2022 final

Final of the 13th edition of the UEFA Women's Championship Football matchUEFA Women's Euro 2022 finalEngland won their first Euro in 2022.EventUEFA Women's Euro 2022 England Germany 2 1 After extra timeDate31 July 2022 (2022-07-31)VenueWembley Stadium, LondonPlayer of the MatchKeira Walsh (England)RefereeKateryna Monzul (Ukraine)Attendance87,192WeatherPartly cloudy25 °C (77 °F)54% humidity[1][2]← 2017 2025 → The UEFA Women's Euro 2022 fi...