Strängstrukturer

Strängstrukturer är de datastrukturer som används för att lagra och manipulera teckensträngar i datorprogram. De beskriver hur tecken lagras i minnet, hur olika operationer som sammanfogning, delsträngar och sökning genomförs samt hur minne och prestanda påverkas av val av representation. Olika språk och bibliotek väljer olika strängstrukturer beroende på användningsområde och krav på snabbhet och minnesutnyttjande.

Den grundläggande representationen är ofta en kontig minnesblock innehållande tecken. En enkel C-stil sträng lagras som en rad tecken följt av en terminator. Andra modeller använder en längd eller ett fält som anger strängens längd för att undvika att söka efter terminatorn. Unicode-tecken kodas vanligtvis med UTF-8, UTF-16 eller UTF-32, vilket påverkar hur operationer som indexering och teckenräkning utförs.

För större eller mer dynamiska textmängder används mer avancerade strukturer. En rope består av ett balanserat träd där varje blad innehåller en substräng; koppling och utdrag av substrängar kan göras utan att kopiera hela innehållet. Gap buffer reserverar en stor buffert och håller en gapad rektangel som flyttas vid insättningar och borttagningar. Piece table kombinerar läsbar källtext med en redigeringsdel i en separat tabell, vilket underlättar historik och effektiv redigering.

Teckenkodningar och normalisering är viktiga aspekter inom strängstrukturer. Olika plattformar och bibliotek stödjer olika teckenkodningar, och jämförelser eller sökningar av strängar kan påverkas av accenttecken, formvarianter och lokala regler. Att bevara korrekt textrepresentation kräver ofta noggrann hantering av teckenkodningar och normalisering.

Prestanda och minnesanvändning varierar med strukturvalet. Kontinuerliga, sammanhängande strängar är ofta snabba för läsning men mindre effektiva vid frekventa ändringar, medan rope, gap buffer och piece table ger bättre redigeringsprestanda på bekostnad av ökat minnesutnyttjande och en mer komplex implementering.