Can I convert long binary strings into unique serial numbers of much shorter length?
3 次查看(过去 30 天)
显示 更早的评论
I’m generating a very large number of long binary strings, for example:
S1 = [0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 …]
S2 = [1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 …]
S3 = …
Sometimes these strings are thousands of elements long and every time I generate a new string I would like to make sure that it is unique and has never been generated before. I could do this by simply storing all strings that has ever existed and using a function like ismember, isequal or something to compare every string to all previous strings, however, this takes a very long time and quickly becomes unfeasible as the list grows.
So I was wondering if there was a faster way of doing this. For example, could I convert every string into a unique serial number of much shorter length somehow so that S1 instead of being represented as a string became the number: 94237 (there is no logic behind this example number) and S 2 some other reasonably short number which perhaps would be much faster to compare uniqueness against than a long string? Is this possible and are there clever conventional ways of converting binary strings into unique serial numbers of minimal length? The serial number does not need to be backwards convertible into the string, all I need is to determine whether or not it is unique.
2 个评论
采纳的回答
Guillaume
2016-9-6
编辑:Guillaume
2016-9-6
Considering that encryptions keys are now getting to 2048 bits or more, 1000 bits is not that long.
How about grouping your bits in lumps of 64. converting that to 64 bits integer, and comparing these 64 bits numbers (with ismember indeed).
If it's not fast enough, then yes any hash function would work. Some, such as md5 are available on the file exchange or can be called directly from matlab using the java interface.
3 个评论
Thorsten
2016-9-6
Guillaume
2016-9-6
You're going to need to generate a LOT of numbers or be really unlucky before you see an md5 collision (as long as you don't deliberately try to create collisions).
And if you see a collision, you can simply compare the true binary vectors. 99.999999% you don't have collisions, so you guaranteed the two vectors are not identical with a fast hash comparison, and once in a blue moon you have a slower comparison.
更多回答(1 个)
Thorsten
2016-9-6
编辑:Thorsten
2016-9-6
You said that you generate the numbers, but you do not mention any constraints on the generation. Without any constraints, just pick a number and append 1 to ensure that the numbers are unique.
If you do have constraints, it would be good to know them. hash functions are fine, but you cannot be 100% sure that there are no collisions, i.e., that you do not generate the same hash for the different inputs. It is just that the hash function tries so minimise the probability of such collisions.
5 个评论
Thorsten
2016-9-6
编辑:Thorsten
2016-9-6
That's exactly what I've suggested. You didn't mention that you need millions of sequences. Do you know in advance an upper limit of the number of sequences you need?
Then you could generate these N unique sequences in decimal reprentation using
seq = randperm(N);
and convert to binary
n = ceil(log2(N))
binseq = dec2bin(seq, n);
and pick from the precomputed list of unique binary sequences, one after the other.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Data Type Conversion 的更多信息
产品
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!