Currently using the run length encoding for encoding bit-vectors, and the current run time is 2log(i), where is the size of the run. Is there another way of doing it to bring it down to log(i)? Thanks.
Efficient way to encode bit-vectors?
1k Views Asked by Chocolate Drop At
1
There are 1 best solutions below
Related Questions in PERFORMANCE
- Slow performance on ipad erasing image
- Can Apache Ant be told to cache its XML files?
- What are the pros and cons of the picture element?
- DB candidate as CouchDB/Schema replacement
- python member str performance too slow
- Split a large query (2 days) into pieces to increase the speed in Postgres
- Use GUI displayed results of SQL query vs new queries?
- fastest way to map a large number of longs
- Bash regular expression execution hangs on long expressions
- Why is calling a function so slow in Javascript?
- Performance of element-compare in java collections
- "Capture GPU Frame" in XCode -- iOS only?
- Efficiency penalty of initializing a struct/class within a loop
- Change the rotating speed of the circle when the mouse moves using javascript
- Replace foreach to make loop into queryable
Related Questions in OPTIMIZATION
- Does compiler optimize operation on const variable and literal const number?
- Optimizing for Social Leaderboards
- 3D FFT with data larger than cache
- Optimum directory structure for large number of files to display on a page
- How to make faster queries on my mysql table?
- Xib taking long time (>1s) to load. UIFont cache seems to blame
- How to speed up string comparisons in an array with a for loop?
- How to load all symbols from shared library on start up?
- Cython speed vs numpy
- Improve Speed of Piecewise Function in MATLAB
- How to check that all values are equal in array using recursion?
- PHP split string into known tokens and remaining words add to single-worded array
- Python: why is my O(n) slowing down as it progresses?
- Hint indexes to mysql on Join
- Error When Compiler Optimizations are on
Related Questions in ENCODING
- how to turn characters in wrong codec into space in python?
- erlang os:cmd() command with UTF8 binary
- How to encode bytes as a printable unicode string (like base64 for ascii)
- weird characters in utf-8 encoded file
- Enforcing that inputs sum to 1 and are contained in the unit interval in scikit-learn
- Detecting corrupt characters in UTF-8 encoded text file
- Why does opening a file in two different encodings work as expected?
- Is there any function like iconv in Python?
- Control encoding when parsing SPSS file using package memisc
- Escape XML on Windows Mobile 6
- MySQL php utf-8 format issues
- Can we convert ANSI encoded CSV file to utf-8 encoded file with javascript?
- How can I compress four floats into a string?
- Represent string as an integer in python
- Character encoding is missing at a point
Related Questions in BITMAP
- How can I extract the bounds of a bitmap in a canvas from the values in the transformation matrix?
- Displaying bitmap image on Android (OpenCV)
- Change color of bitmap by color Transform Matrix not working
- TImagelist for large images
- crop bitmap in screen size from custom width
- Bitmap too large to be uploaded into a texture (3000x1547, max=2048x2048)
- Converting Bitmap to ByteArray and back to Bitmap not working
- Trying to make a random pixel in a bitmap a new color, but it is giving an error why
- Resizing images failing on start, setContentView & bitmap factory[android]
- Pass image URL/URI from Activity A to open as Image in Activity B Android
- Draw cirble bitmap in onDraw() ImageView without creating another bitmap
- android Bitmap Subsampling of Image
- fast converting Bitmap to BitmapSource wpf
- How to save image to sdcard when using Fresco?
- How to check each bit in 16 bit address in C
Related Questions in BITVECTOR
- Bit match analogue for array of words (fingerprints)
- bit vector intersect in handling parquet file format
- Multiple bitvectors; how to find bits that are set exactly n times?
- Timeout while reasoning about arrays and bitvectors in z3
- When should I use a BitVector32?
- Bit array Vs Bit vector
- BitVec incorrectly appends 0s instead of 1s
- Convert BitArray to integer in PowerShell
- Explain the use of a bit vector for determining if all characters are unique
- Determining a string has all unique characters without using additional data structures and without the lowercase characters assumption
- Z3: Convert int sort into bitvector
- My code is not leaving the loop that starts at line 228 (called ciclo), it seems like it's not reading the mouse
- Bitvector32 and Bitarray in C#
- BitVector library, changing value in splice of BitVector
- ModuleNotFoundError when running code, but works in ipython
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
The most efficient way of encoding a bit vector is to isolate any specific properties of the bit source. If it is totally random, there is no real noticeable gain (actually, a totally random stream of bit cannot be compressed in any way).
If you can find properties in your bit stream you could try to define a collection of vectors which will define the base of a Vector Space. In such case, the result will be very efficient.
We'll need a few more details on your bit stream.
(Edit)
Just a few more details to understand the previous statement: "a totally random stream of bits cannot be compressed in any way"
It is not possible to compress a totally random vector of bits if by "compress" we mean the "transformed/compressed stream" plus the "vector base definition" plus the decompression program. But in most cases the decompression program (and often the vector base too) is embedded in client software. Thus, only the "compressed stream" is needed.
A good explanation (and funny story) about that is Patrick Craig 5000$ compression challenge
More scientific the theory of information, especially entropy section
And, the final one, the full story.
But whatever the solution is, if you have an unknown number of unknown streams to compress you won't be ale to do anything. You have to find a pattern.