2c:null 2d:["$","title",null,{"children":"Bit Bunching Compression V0.1 | notanaccent | Observable"}] 32:T6b8,md`#### Field types: Encoding is applied to each data point to tranform it from an arbitrary value to an unsigned integer of minimum bits. In the following functions *v* is the encoded value, *index* the row number, and *meta* the automatically generated metadata. Each field may be given a type completely independant of the others. * **enum**. Can be a number or string. Will be encoded as an index to a look up table of unique values, and decoded to the original value. This can result in an extremely small encoded size if used on data fields with relatively few unique values. ~~~js (v, index, meta) => meta.lut.indexOf(v) ~~~ * **integer**. Must be a number or +castable as a number. Will be rounded to a whole number difference from the minimum value in the field. This is a good choice for fields such as id that are whole numbers and must preserve their value exactly. ~~~js (v, index, meta) => v + meta.datum ~~~ * **float**. Must be a number or +castable as a number. Will become a floating-point-like value (definately not IEEE 754 standard) with precision as defined or 1/65000 the field's range. This is a good choice for fields representing continuous values, such as location or time. A larger value for precision will reduce the overall file size. ~~~js (v, index, meta) => (v * meta.precision) + meta.datum ~~~ * **index**. Must be a number or +castable as a number and should change linearly with data index. This is a good choice for a field increasing or decreasing perfectly linearly in sorted data, such as an id, index, or timestamp. This field type is encoded entirely in metadata and has negligible affect on overall file size. ~~~js (v, index, meta) => index * meta.gain + meta.datum ~~~ `33:T44a,{ const spinner = html``; return Generators.observe((next) => { next(table()); spinner.onchange = () => next(table()); }); function table() { return html`

${md` Comparison of data index ${spinner} before and after compression. |Field|Encoding Type|Precision Specified|Before|After|Change|Pass| |-----|-------------|---------|:----:|:---:|:----:|:------:| ${configuration .map((c) => { const before = data[+spinner.value][c.field]; const after = decompressed[+spinner.value][c.field]; const diff = after - before; const pass = c.precision ? Math.abs(diff) <= c.precision : before === after; return ( "|" + [ c.field, c.type, c.precision, before, after, diff, String.fromCodePoint(parseInt(pass ? "2714" : "274C", 16)) ].join("|") + "|" ); }) .join("\n")} `}

`; } }34:Taa4,function decompress( { bytesPerRow, numberOfRows, zipped, dataURL, meta }, startRow, endRow ) { //default, decompresses all let start = startRow || 0; let end = endRow || numberOfRows; //negative indexing start = start < 0 ? start + numberOfRows : start; end = end < 0 ? end + numberOfRows : end; for (let i in meta) { // un-JSON the post-processing functions if (typeof meta[i].postProcess !== "function") { meta[i].postProcess = eval(meta[i].postProcessString); } } return new Promise(function (resolve) { // promise decoded data const reader = new FileReader(); reader.onloadend = () => resolve(getRows(reader.result, start, end)); if (zipped) { dataURLToBlob(dataURL) .then(decompressBlob) .then((blob) => reader.readAsArrayBuffer(blob)); } else { dataURLToBlob(dataURL).then((blob) => reader.readAsArrayBuffer(blob)); } }); function getRows(buffer, startIndex, endIndex) { const byteArray = new Uint8Array(buffer); const span = endIndex - startIndex; const rows = Array(span); for (let i = 0; i < span; i++) { rows[i] = getRow(byteArray, startIndex + i); } return rows; } function getRow(byteArray, index) { const row = {}; const subArray = byteArray.subarray( index * bytesPerRow, (index + 1) * bytesPerRow ); for (let j = 0; j < meta.length; j++) { row[meta[j].field] = getValue(subArray, index, meta[j]); } return row; } function getValue(subArray, index, fieldMeta) { if (fieldMeta.type === "index") { return index * fieldMeta.gain; } else { let intValue = 0; for (let i = 0; i < bytesPerRow; i++) { const m = fieldMeta.mask[i]; if (m) { intValue += (m & subArray[i]) * 2 ** (fieldMeta.endBit - 8 * (i + 1)); } } const value = unpackValue(intValue, index, fieldMeta); return fieldMeta.postProcess ? fieldMeta.postProcess(value) : value; } } function unpackValue(intValue, index, fieldMeta) { switch (fieldMeta.type) { case "index": return index * fieldMeta.gain; case "integer": return intValue + fieldMeta.datum; case "float": return intValue * fieldMeta.precision + fieldMeta.datum; case "enum": return fieldMeta.lut[intValue]; default: return undefined; } } function dataURLToBlob(dataURL) { return fetch(dataURL).then((r) => r.blob()); } function decompressBlob(blob) { const format = zipped === "deflate" ? "deflate" : "gzip"; return new Response( blob.stream().pipeThrough(new window.DecompressionStream(format)) ).blob(); } }35:T14c6,function compress(dataset, config, { zip } = {}) { const { bytesPerRow, meta } = prepare(dataset, config); createMasks(meta, bytesPerRow); const buffer = new ArrayBuffer(bytesPerRow * dataset.length); const view = new DataView(buffer, 0, bytesPerRow * dataset.length); for (let i = 0; i < dataset.length; i++) { setRow(view, dataset[i], i); } return new Promise((resolve) => { const blob = new Blob([buffer]); const result = zip ? compressBlob(blob).then(blobToDataURL) : blobToDataURL(blob); result.then((dataURL) => resolve({ numberOfRows: dataset.length, bytesPerRow, zipped: zip, meta, //config, // optional //compress, // optional decompress: `(${decompress.toString()})`, documentation: "https://observablehq.com/@notanaccent/bit-bunching-compression", dataURL }) ); }); function setRow(view, dataRow, index) { let binaryRow = ""; for (let j = 0; j < meta.length; j++) { binaryRow += encodeValue(dataRow[meta[j].field], index, meta[j]); } while (binaryRow.length < bytesPerRow * 8) { binaryRow += "0"; } for (let i = 0; i < bytesPerRow; i++) { view.setUint8( index * bytesPerRow + i, parseInt(binaryRow.slice(i * 8, i * 8 + 8), 2) ); } } function encodeValue(dataPoint, index, fieldMeta) { const integerValue = packValue(dataPoint, index, fieldMeta) || 0; let binaryValue = Math.round(integerValue) .toString(2) .slice(0, fieldMeta.length); while (binaryValue.length < fieldMeta.length) { binaryValue = "0" + binaryValue; } return binaryValue; } function packValue(dataPoint, index, fieldMeta) { switch (fieldMeta.type) { case "index": return (index - fieldMeta.datum) / fieldMeta.gain; case "integer": return +dataPoint - fieldMeta.datum; case "float": return (+dataPoint - fieldMeta.datum) / fieldMeta.precision; case "enum": return fieldMeta.lut.indexOf(dataPoint); default: return undefined; } } function prepare(dataset, config = []) { // TODO autodetect best config const meta = []; let offset = 0; for (let c of config) { let slot = { field: c.field, type: c.type, length: 0 }; if (typeof c.postProcess === "function") { slot.postProcessString = `(${c.postProcess.toString()})`; } if (c.type === "enum") { slot.lut = Array.from(unique(dataset.map((d) => d[c.field]))); slot.length = Math.ceil(Math.log(slot.lut.length) / Math.log(2)); } else { const d0 = +dataset[0][c.field]; const min = dataset.reduce((a, d) => Math.min(a, +d[c.field]), d0); const max = dataset.reduce((a, d) => Math.max(a, +d[c.field]), d0); const range = max - min; slot.datum = min; switch (c.type) { case "integer": slot.length = Math.ceil(Math.log(range) / Math.log(2)); break; case "float": // TODO absolute deviation polynomial regression slot.precision = c.precision || range / 2 ** 16; slot.length = Math.ceil( Math.log(range / slot.precision) / Math.log(2) ); break; case "index": const gain2 = c.gain || range / (dataset.length - 1); slot.gain = gain2; slot.length = 0; break; default: throw ( "Bad type <" + c.type + "> for field <" + c.field + "> during preperation for data encoding." ); } } slot.offset = offset; offset += slot.length; meta.push(slot); } const bytesPerRow = Math.ceil(offset / 8); return { bytesPerRow, meta }; } function createMasks(meta, bytesPerRow) { for (let i = 0; i < meta.length; i++) { let fieldMeta = meta[i]; fieldMeta.mask = []; const { field, offset, length } = { ...fieldMeta }; const start = Math.floor(offset / 8), end = Math.ceil((offset + length) / 8), rem = (8 - ((offset + length) % 8)) % 8; fieldMeta.endBit = offset + length; for (let b = 0; b < bytesPerRow; b++) { let mask = b < start || b >= end ? 0x00 : b === start && b === end - 1 ? ((0xff >> offset % 8) >> rem) << rem : b === start ? 0xff >> offset % 8 : b === end - 1 ? (0xff >> rem) << rem : 0xff; fieldMeta.mask.push(mask); } } } function unique(arr) { // could also use d3.union const dict = {}; for (let i = 0; i < arr.length; i++) { dict[arr[i]] = true; } return Object.keys(dict); } function blobToDataURL(blob) { return new Promise((resolve) => { const reader = new FileReader(); reader.onload = (e) => resolve(e.target.result); reader.readAsDataURL(blob); }); } function compressBlob(blob) { const format = zip === "deflate" ? "deflate" : "gzip"; return new Response( blob.stream().pipeThrough(new window.CompressionStream(format)) ).blob(); } }36:[{"id":"43d3e5ed3a6da3118d2bb4e51e0265265f08920e8419e8c0852d8c46523e3529b641e312f3a262deb4d2286e6b69c74aba33b99bd42e7316d37b812864573d65","href":"https://static.observableusercontent.com/files/43d3e5ed3a6da3118d2bb4e51e0265265f08920e8419e8c0852d8c46523e3529b641e312f3a262deb4d2286e6b69c74aba33b99bd42e7316d37b812864573d65","name":"inaturalist.csv","type":"text/csv","lastModified":1631173152743.003,"size":3918432}] 30:{"id":"ed55f0a199e4e519","slug":"bit-bunching-compression","title":"Bit Bunching Compression V0.1","thumbnail":"051661b4bb9a837e141b65c0310a86b0f73b6619d2d02f6b65b5759eaa3dd310","access_level":"public","create_time":"$D2021-09-04T08:27:50.113Z","update_time":"$D2022-03-23T00:40:58.680Z","view_time":null,"first_public_time":"$D2021-09-09T11:55:03.645Z","has_unpublished_edits":null,"fork":false,"stars":4,"starred":false,"owner":{"type":"team","id":"bc6b9021599bcf55","login":"notanaccent","name":"","avatar_url":"https://avatars-next.observableusercontent.com/b94c500c7691cb0a3e4d8b84b846c7171a4f09348a3b5be1110d9874e6195351","tier":"starter_2024"},"version":3214,"publish_version":3214,"role":null,"authored":false,"authors":[{"type":"individual","id":"ce955889d463ad2d","login":"notanaccent","name":"","avatar_url":"https://avatars-next.observableusercontent.com/b94c500c7691cb0a3e4d8b84b846c7171a4f09348a3b5be1110d9874e6195351","tier":null}],"members":[{"type":"individual","id":"ce955889d463ad2d","login":"notanaccent","name":"","avatar_url":"https://avatars-next.observableusercontent.com/b94c500c7691cb0a3e4d8b84b846c7171a4f09348a3b5be1110d9874e6195351","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":{"id":"bf73a325b33db923","slug":"compression","title":"Compression","owner":{"id":"bc6b9021599bcf55","login":"notanaccent","name":""}},"type":"notebook","body":{"titling":"auto","title":"Bit Bunching Compression V0.1","cells":[{"id":0,"value":"# Bit Bunching Compression V0.1\nSquishing bytes for an easy reduction in file size.\n\n* mostly hands-off\n* field-by-field encoding type\n* transportable as JSON \n* built in decompressor\n* data can be decompressed in slices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2805,"value":"md`~~~js\n import {compress, decompress} from \"@notanaccent/bit-bunching-compression\"\n~~~`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2811,"value":"md`\nSimilar Notebooks:\n* [iNaturalist Phenology](https://observablehq.com/@notanaccent/inaturalist-phenology) - a visualization using this compression\n* [Zip Unzip](https://observablehq.com/@notanaccent/zip-unzip) - standard browser-based compression.\n\nFeedback welcome!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1878,"value":"md`### Compressing\nPass data and a configuration to the compressor. The resulting object includes the data as a dataURL along with metadata and a decompressor.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2524,"value":"compressed = compress(data, configuration, { zip: false })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":522,"value":"md`The compressed data object as JSON is ${(jsonData.length / 1024).toFixed(\n 0\n)}KB, **${(\n (100 * jsonData.length) /\n (await source.text().then((text) => text.length))\n).toFixed(\n 1\n)}%** of the source file size. If compatability is not a concern, enable the **zip** parameter to further reduce file size using [Compression Streams](https://developer.mozilla.org/en-US/docs/Web/API/Compression_Streams_API).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2581,"value":"jsonData = JSON.stringify(compressed)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":565,"value":"DOM.download(\n new Blob([jsonData], { type: \"text/json\" }),\n \"compressed_data.json\",\n \"Download compressed_data.json\"\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1874,"value":"md`### Decompressing\nData may be retrieved at its destination using the embeded decompressor. Verification of the decompressed data is below.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":493,"value":"decompressed = eval(compressed.decompress)(compressed)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3105,"value":"md`Decompressing slices of large datasets may be preferable.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3110,"value":"decompressedSlice = eval(compressed.decompress)(compressed, 5, 10)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2700,"value":"md`### Data \nThe example data is 35k citizen science animal observations from iNaturalist. A decade of mammal observations in British Columbia exports as a 3.7MB csv file.
\nSource: [iNaturalist.org](https://inaturalist.ca/observations/export)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":535,"value":"source = FileAttachment(\"inaturalist.csv\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2705,"value":"md`For better results, data is preprocessed before being compressed:\n* turn unecessary strings into numbers (or types castable as numbers)\n* concat fields that correlated (eg. scientific & common names for species)\n* sort by a linear field, to leverage the index encoding type`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2698,"value":"data = source.csv().then((dataSet) =>\n dataSet\n .filter((d) => d.time_observed_at) // rows with bad dates are removed\n .map((d, i) => {\n // Firefox needs this to read the dates, thanks Rahul\n // https://stackoverflow.com/a/21984717\n const dateString = d.time_observed_at.replace(/-/g, \"/\");\n\n // Dates are more efficiently encoded as numbers and the Date Object\n // becomes a number automatically when encoded as \"integer\", \"float\", or \"index\"\n d.time_observed_at = new Date(Date.parse(dateString));\n\n // added to demonstrate an index field\n d.example_index = i * 4;\n\n // These fields are almost always matched, combining them will further reduce file size\n d.species = [d.scientific_name, d.common_name].join(\",\");\n return d;\n })\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1765,"value":"md`### Encoding Scheme\nAssuming table-like data, columns are named fields and rows are allocated a fixed number of bytes. \n\nWithin the row:\n* the encoder assigns a minimum number of bits to represent each data field to the precision and type specified during configuration.\n* bits allocated to each field do are not necessarily divisible by 8.\n* total allocation is rounded to the next whole byte.\n\nThe resulting bit mask generated for this data, is shown below as binary strings:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2394,"value":"html`\n

${md`#### Bit Mask \n\n|Field|${[...Array(compressed.bytesPerRow).keys()]\n .map((i) => \"Byte \" + i)\n .join(\"|\")}\n|${[...Array(compressed.bytesPerRow + 1).keys()].map((i) => \"---\").join(\"|\")}\n${compressed.meta\n .map(\n (m) =>\n `|${m.field}|

${m.mask\n        .map((b) => {\n          let str = b.toString(2);\n          while (str.length < 8) {\n            str = \"0\" + str;\n          }\n          return str;\n        })\n        .join(\"

\")}

|`\n )\n .join(\"\\n\")}`}

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1885,"value":"md`### Configuration\nThe compressor is configured with a list of field settings. \n\nIn order to be included in the compressed data, the corresponding *field* in the source data must be listed and assigned a *type*. \n\nAn optional *postProcess* function may be defined which will be applied to all datapoints in that field after decompression.\n\nField type *float* may include a minimum *precision*. If defined, the precision will be at least as good as this number and up to twice as good depending on how the bits work out. If not defined, the precision will be about 1/65000 the range of the field.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":334,"value":"configuration = [\n { field: \"id\", type: \"integer\", postProcess: (d) => d.toString() },\n {\n field: \"time_observed_at\",\n type: \"float\",\n precision: 6e4,\n postProcess: (d) => new Date(d)\n },\n { field: \"quality_grade\", type: \"enum\" },\n { field: \"latitude\", type: \"float\", precision: 6e-4 },\n { field: \"longitude\", type: \"float\", precision: 4e-4 },\n { field: \"species\", type: \"enum\" },\n { field: \"example_index\", type: \"index\" }\n]","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":552,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2779,"value":"verification = md`### Verification`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3151,"value":"md`The following cell tests that each decompressed value matches the original value exactly, or within the specified precision for field type **float**.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":977,"value":"tests = {\n const validity = data.map((d, i) =>\n Object.fromEntries(\n configuration.map((c) => [\n c.field,\n c.type === \"float\"\n ? decompressed[i][c.field] - d[c.field] < c.precision\n : decompressed[i][c.field] === d[c.field]\n ])\n )\n );\n const failIndex = validity\n .map((v) => Object.values(v).every((t) => t))\n .indexOf(false);\n return failIndex === -1 ? \"passed\" : \"failed at index \" + failIndex;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1866,"value":"md`### Source`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1"}} 31:"$30:body"