Beknopte weergave

Bij gegevensverwerking, heet beknopte weergave van een gegevensstructuur van een bepaald opslagschema van hetzelfde, zodat de ingenomen ruimte is vergelijkbaar met de theoretische ondergrens en toch is het mogelijk om de typische werking van de constructie op een efficiënte wijze uitvoeren.

Voor binaire bomen

Het meest klassieke voorbeeld van wat beknopte weergave van binaire bomen: het aantal binaire bomen met n knooppunten verschillend, die asymptotisch toeneemt naarmate de theoretische ondergrens geheugen nodig is ongeveer

bits per boom, of 2 bits per node.

Deze limiet is gemakkelijk te bereiken met de volgende code:

  • Allereerst is "verzadigd" de grafiek door het toevoegen van nodes placeholder bij elke vertakking afwezig
  • dan maak je een breedte boom gewijzigd en geschreven in een speciale string een 1 per node waar en een 0 voor elke placeholder bezocht

Zo wordt de beknopte weergave van de structuur aan de rechterzijde door de string:

Het komt goed, dat zo'n notatie produceert een reeks bits precies, en u kunt dan overwegen beknopt. Het is duidelijk dat deze representatie betreft de structuur van de boom en geen gegevens of labels die de grafiek knooppunten bevatten; Deze kunnen worden opgeslagen in een array, in de volgorde waarin ze worden bezocht door de breedte.

Dit resultaat kan worden gegeneraliseerd naar elke bomen.

Voor grafieken

Bij gerichte grafen met n hoekpunten genummerd, de beknopte weergave is veel eenvoudiger en wordt gegeven door adjacentiematrix. Plaats n het aantal hoekpunten van de grafiek worden de mogelijke gerichte grafen exact genummerd, of precies zoveel als matrices met alleen 0 en 1.

De ongerichte grafieken zijn genummerd, en een beknopte weergave perfect wordt gegeven door de bovenste driehoekige deel van de adjacentiematrix.

De spraak duidelijk complexer bij grafieken niet geteld, aangezien het moeilijk is om te bepalen wanneer bestaat er een isomorfisme tussen twee grafieken niet geteld, en er zijn soorten niet-isomorfe grafieken. Maar het is bekend dat het aantal bits dat nodig is om een ​​grafiek ongenummerde caudaal wordt beperkt en dat er efficiënt coderen voorstellingen die deze limiet bereikt.

(0)
(0)
Commentaren - 0
Geen reacties

Voeg een Commentaar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha