RLE compression

compress.test.ts

import { compress, decompress } from './compress'

test('basic-compress', () => {
	const input = [100, 0, 0, 0, 43, 4, 43, 43]
	expect(compress(input)).toBe('100,0:3,43,4,43:2')
})

test('long-compress', () => {
	const longInput = [
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
	]
	expect(compress(longInput)).toBe('0:176')
})

test('singleton-compress', () => {
	const input = [10]
	expect(compress(input)).toBe('10')
})

test('another-compress', () => {
	const input = [4, 868, 100, 100, 101]
	expect(compress(input)).toBe('4,868,100:2,101')
})

test('simple-decompress', () => {
	const compressed = '2,35,9:12,1111'
	expect(decompress(compressed)).toStrictEqual([
		2, 35, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 1111
	])
})

test('singleton-decompress', () => {
	const compressed = '2'
	expect(decompress(compressed)).toStrictEqual([2])
})

test('round-trip', () => {
	const input = [1, 1, 2, 3, 5, 8]
	expect(decompress(compress(input))).toStrictEqual(input)
})

compress.ts

/**
 * Separator for the numbers
 */
const delimiter = ','

/**
 * Returns a compressed string representation of the
 * given array using RLE. Look at compress.test.ts
 * for examples
 * @param arr an array of numbers
 */
export function compress(arr: number[]): string {
	if (!arr || arr.length === 0) {
		return ''
	}
	const sb = []
	let i = 0
	// j is always 1 ahead of i
	let j = 1
	while (i < arr.length - 1) {
		const currNum = arr[i]
		// compression is achieved by storing
		// the count of consecutive appearances
		// of a given number
		let numRepeated = 1
		while (j < arr.length && arr[j] === currNum) {
			j++
			numRepeated++
		}
		if (numRepeated === 1) {
			sb.push(`${currNum}`)
		} else {
			sb.push(`${currNum}:${numRepeated}`)
		}
		i = j
		j = i + 1
	}
	if (i === arr.length - 1) {
		// last element, just push it
		sb.push(`${arr[i]}`)
	}

	return sb.join(delimiter)
}

/**
 * Expands the number and length to an array structure
 * @param rleItem the number and its length separated by a colon
 */
function expand(rleItem: string): number[] {
	const numAndCount = rleItem.split(':')
	const radix = 10
	if (numAndCount.length === 0 || numAndCount.length > 2) {
		throw new Error(`Got invalid RLE encoding. Element: ${rleItem}`)
	}
	if (numAndCount.length === 1) {
		// this means that the count is 1
		return [parseInt(numAndCount[0], radix)]
	}
	const num = parseInt(numAndCount[0], radix)
	const count = parseInt(numAndCount[1], radix)

	const expanded: number[] = []
	for (let i = 0; i < count; i++) {
		expanded.push(num)
	}
	return expanded
}

/**
 *  The opposite of compress
 * @param str compressed array
 */
export function decompress(str: string): number[] {
	const strArr = str.split(delimiter)
	let numArr = []
	strArr.forEach(s => {
		const expanded = expand(s)
		numArr = numArr.concat(expanded)
	})

	return numArr
}