Мне было интересно, есть ли лучший способ сделать это в NodeJS или в простом JavaScript.
Я написал несколько функций, которые могут делать это, подсчитывая, сколько раз они повторяются, но мне было интересно, есть ли лучший способ или можно ли внести какие-либо улучшения.
Входные данные всегда будут представлять собой 256-битную числовую строку, состоящую только из 1 и 0 ('00001110100101.....').
function toSmallString(x) { // {{{
return new Promise((resolve, reject) => {
// always start with a 0 or a 1 to show bigstring where to start
var nn = `${x[0]}`;
var ar = x.split('')
var n = 0;
var lv = ar[0];
// a blank item to iterate, catches the last set of numbers
ar.push('')
// 0 means ten and continue since we will always be above 1
for (const v of ar) {
// if flipping bits, store number and start over
if (lv !== v) { nn += n ;lv = v; n = 1 }
// increment if last value is same as this value, if value becomes 10, add a 0 to nn and start over
else { n = n + 1;if (n === 10){nn += '0';n = 0} }
}
resolve(nn)
})
}
function toBigString(x) {
return new Promise((resolve, reject) => {
var ar = x.split('')
var sn = parseInt(ar.shift())
var nn = ''
// 0 means 10 zeros and continue without bitflipping
// any other number will expand and then flip bits
for (const v of ar) {
var n = parseInt(v)
var i = 1
if (n === 0){
nn += sn.toString().repeat(10)
} else {
while(i <= n){
nn += sn
i = i + 1
}
// bit flip
sn = (sn === 0) ? 1 : 0;
}
}
resolve(nn)
})
}
Я попробовал пару вещей, я очень неопытен (шестнадцатеричное, научное обозначение), но значения меняли форму при попытке преобразовать их обратно в исходные 256 бит 1 и 0.
каждая цифра 1 и 0 важна, их расположение и порядок крайне важно сохранить.
Мой план состоит в том, чтобы хранить сотни тысяч этих 256-битных строк, поэтому лучше всего использовать сжатие строк.
Редактировать: Вот список из примерно 7 тыс. входных строк
теперь, когда я думаю об этом, скорее 70 или 80 лет.
@Pointy мой алгоритм сжатия оказался немного лучше для этого конкретного случая использования. Благодарю вас за ваше усилие
Простым решением может быть использование BigInt (который может безопасно представлять 256-битное число), а затем преобразовать его в шестнадцатеричную строку.
function toSmallString(x) {
return BigInt('0b' + x).toString(16); // bin => hex
}
function toBigString(x) {
return BigInt('0x' + x).toString(2).padStart(256, '0'); // hex => bin
}
Вы можете использовать еще большее основание системы счисления (до 36), чтобы сделать его потенциально еще короче.
Спасибо, однако после использования этого ~ 7 тысяч раз было ~ 5 тысяч случаев, когда распакованный номер больше не совпадал. вот csv список случаев, когда они не совпадали. значения располагаются в следующем порядке: «исходное|сжатое|распакованное». Я обновляю исходный пост, чтобы включить полный список из ~ 7 тыс.
@RadicalEdward Верно, он удалял ведущие нули. Исправлено сейчас.
@AHaworth Я думал об этом, но похоже, что для BigInt нет parseInt
эквивалента, где можно указать систему счисления. Только старое предложение на одного...
Обновлять
я расширил решение @Nikk и решил использовать шестнадцатеричный формат
Цель состоит в том, чтобы получить максимально короткую строку из строки, которая будет содержать только диапазон цифр (первоначально 0-1, но в этом примере мы сделаем 1-8).
Я определил карту символов, содержащую все возможные двухзначные комбинации от 11 до 88 (11..18,21..28,31.......88), которая сопоставляет ее с одним символом, в ней 64 возможных комбинации. этот диапазон (8^2=64)
поэтому со всеми возможными комбинациями наш окончательный набор символов стал [a-zA-Z!-_] без каких-либо цифр.
наша длина меняется с 256 на 128
мне было бы интересно попробовать сопоставить большие наборы цифр с юникодом символы, чтобы получить более короткие результаты, но нам нужно гораздо больше карта персонажей.
поскольку в нашем наборе символов нет чисел, мы можем переключать повторяющиеся символы с помощью одного символа и цифры, чтобы указать, сколько раз этот символ повторяется.
поскольку наша цифра всегда будет равна 1 и выше, мы можем сказать, что 0 означает 10, а затем помещать еще одну цифру, пока они в сумме не дадут точное повторение.
это означает, что наши цифры 0.... и 1.... станут a4 и b4 40 повторений 1 превращаются в a0000 ('0' * 10 в 4-й степени) 100 повторений 1 превращаются в a0000000000 ('0' * 10 в 10-й степени) 256 0s будут a00000000000000000000000006, что представляет собой строку длиной 27 бит.
поэтому при таком подходе наша результирующая строка из 256 бит будет варьироваться от 27 до 128 бит.
мы могли бы стать короче, заменив повторяющиеся 0 на набор значений Юникода, поскольку это более крупный набор символов, в результате чего самая короткая строка будет выглядеть примерно так: «a0|6»
«a0|6» означает 256 нулей подряд, однако мы могли бы просто сохранить одну цифру и повторить ее 256 раз при возврате в случае, если все цифры совпадают.
Таким образом, самая короткая строка варьируется от 1,4 до 128 бит от 256 цифр, причем более короткие строки возможны только в том случае, если в строке более 4 повторяющихся цифр. (что я делаю очень часто)
вот код для сжатия строк base8 (1-8)
function allCharactersSame(s){
let n = s.length;
for (let i = 1; i < n; i++) {
if (s[i] != s[0]) {
return false;
}
return true;
}
}
const characterMap = { // {{{
'11':'a','12':'b','13':'c','14':'d','15':'e','16':'f','17':'g','18':'h','21':'i','22':'j','23':'k','24':'l','25':'m','26':'n','27':'o','28':'p','31':'q','32':'r','33':'s','34':'t','35':'u','36':'v','37':'w','38':'x','41':'y','42':'z','43':'A','44':'B','45':'C','46':'D','47':'E','48':'F','51':'G','52':'H','53':'I','54':'J','55':'K','56':'L','57':'M','58':'N','61':'O','62':'P','63':'Q','64':'R','65':'S','66':'T','67':'U','68':'V','71':'W','72':'X','73':'Y','74':'Z','75':'!','76':'@','77':'#','78':'$','81':'%','82':'^','83':'&','84':'*','85':'(','86':')','87':'-','88':'_'
} // }}}
async function convertHash(string) { // {{{
if (allCharactersSame(string)){
return string[0]
}
if (string.length % 2 === 1){throw 'Input MUST be fully divisable by 2'}
var n = ''
// map characters
string.match(/.{1,2}/g).forEach((num) => {n += characterMap[num]})
// shrink repeats
string = n.replace(/(.)\1+/g, (s) => {
var nn = ''
var x = Math.floor(s.length / 10)
var y = s.length % 10
nn += '0'.repeat(x)
if (y !== 0){nn += y}
return `${s[0]}${nn}`
})
return string
} // }}}
async function revertHash(string) { // {{{
if (string.length === 1){
return string.repeat(256)
}
// unshrink
var nn = string.replaceAll(/([a-zA-Z])([0-9]+)/g,function(s1){
var ny = ''
var v = '';
var ar = s1.split('')
var ch = ar.shift()
for(v of ar) {
if (v === '0'){
ny += ch.repeat(10)
} else {
ny += ch.repeat(v)
}
}
return ny
})
// unpack
var n = ''
nn.split('').forEach(bit => {
Object.keys(characterMap).forEach(key => {
if (bit === characterMap[key]) {
n += key
}
})
})
return n
} // }}}
Используя это, я сжал ~7 тыс. 256-битных числовых строк в кодировке Base2 в среднем до 86 бит, причем ~30 из них стали однобитными с точностью 100% при распаковке.
Я очень неопытен — понимаю, что схемы сжатия данных были областью чрезвычайно активных исследований в течение как минимум 40 лет. Приятно, что вы хотите сделать что-то интересное, но существует огромное количество существующих работ, на которые стоит обратить внимание. Проверьте Википедию, например, в разделе «Сжатие данных».