|
|
`oops` -- The runtime you wanted for C.
|
|
|
|
|
|
# Description
|
|
|
|
|
|
`oops` provides various utilities, data structures and algorithms for rapid prototyping of CLI applications in C99 under Linux.
|
|
|
|
|
|
# Debian/Ubuntu repository
|
|
|
|
|
|
We provide pre-compiled binaries for Debian/Ubuntu `amd64` architectures.
|
|
|
|
|
|
Please follow [these instructions](https://www.uvolante.org/apt) to add the repository to your system.
|
|
|
|
|
|
# Utilities
|
|
|
|
|
|
`oops` includes CLI options management, and a dispatch queue[^1] for easy multithreading.
|
|
|
|
|
|
# Generic data structures
|
|
|
|
|
|
`oops` provides vectors, matrices, lists, stacks, queues, (binary) trees, graphs, iterators, and suffix arrays[^2].
|
|
|
|
|
|
# Algorithms
|
|
|
|
|
|
`oops` contains:
|
|
|
* basic combinatorics (permutations and combinations)
|
|
|
* codecs (Elias gamma[^3], Simple9[^4], Huffman{[^5]<sup>,</sup>[^6], LZ77[^7]<sup>,</sup>[^8], DEFLATE[^9], gzip[^10])
|
|
|
* a relative LZ[^11]<sup>,</sup>[^12] coder
|
|
|
* an implementation of the PC algorithm for causality inference[^13]
|
|
|
|
|
|
# Task list
|
|
|
|
|
|
- [x] Release first version
|
|
|
- [ ] Data compression
|
|
|
- [ ] Add native gzip/csa I/O
|
|
|
- [ ] Trees
|
|
|
- [ ] Prim's minimum spanning tree
|
|
|
- [ ] Clustering and data analysis
|
|
|
- [ ] DPRT
|
|
|
- [ ] Robust PCA
|
|
|
- [ ] ICA
|
|
|
- [ ] Image
|
|
|
- [ ] Provide basic structure
|
|
|
- [ ] PGM I/O
|
|
|
- [ ] JFIF codec
|
|
|
- [ ] Psycho-visual masking
|
|
|
- [ ] SURF descriptors
|
|
|
- [ ] Linear algebra
|
|
|
- [ ] Gram-Schmidt procedure
|
|
|
- [ ] Rank-revealing (parallel?) QR
|
|
|
- [ ] LU
|
|
|
- [ ] SVD
|
|
|
- [ ] Random numbers
|
|
|
- [ ] Implement MT19937
|
|
|
- [ ] Look at Wallace for Gaussian generation (or keep Ziggurat)
|
|
|
- [ ] Watermarking
|
|
|
- [ ] Implement basic methods
|
|
|
- [ ] Assembly
|
|
|
- [ ] VM for ASM emulation
|
|
|
- [ ] Lambda calculus
|
|
|
- [ ] Start implementing Ghuloum papers
|
|
|
|
|
|
# References
|
|
|
|
|
|
[^1]: Bil Lewis and Daniel J. Berg, "Threads Primer: A Guide to Multithreaded Programming", ISBN-13 978-0134436982, Prentice Hall, October 1995.
|
|
|
|
|
|
[^2]: Juha Kärkkäinen and Peter Sanders, "Simple Linear Work Suffix Array Construction", Proc. 30th International Colloquium on Automata, Languages and Programming, ICALP'03, LNCS 2719, Springer, pp. 943--955. :leftwards_arrow_with_hook:
|
|
|
|
|
|
[^3]: Peter Elias, "Universal Codeword Sets and Representations of the Integers", IEEE Transactions on Information Theory, vol. 21, No. 2, pp. 194--203, March 1975.
|
|
|
|
|
|
[^4]: Vo Ngoc Anh and Alistair Moffat, "Inverted Index Compression Using Word-Aligned Binary Codes", Information Retrieval, vol. 8, issue 1, pp. 151--166, January 2005.
|
|
|
|
|
|
[^5]: David A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., vol. 40, No. 2, pp. 228--230, September 1952.
|
|
|
|
|
|
[^6]: Eugene S. Schwartz and Bruce Kallick, "Generating a Canonical Prefix Encoding", Communications of the ACM, vol. 7, issue 3, pp. 166--169, March 1964.
|
|
|
|
|
|
[^7]: Jacob Ziv and Abraham Lempel, "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. 23, No. 3, pp. 337--343, May 1977.
|
|
|
|
|
|
[^8]: Maxime Crochemore and Lucian Ilie, "Computing Longest Previous Factor in Linear Time and Applications", Information Processing Letters, vol. 160, issue 2, pp. 75--80, April 2008.
|
|
|
|
|
|
[^9]: L. Peter Deutsch, "DEFLATE Compressed Data Format Specification version 1.3", RFC1951, May 1996.
|
|
|
|
|
|
[^10]: L. Peter Deutsch, "GZIP file format specification version 4.3", RFC1952, May 1996.
|
|
|
|
|
|
[^11]: Jacob Ziv and Neri Merhav, "A Measure of Relative Entropy between Individual Sequences with Application to Universal Classification", IEEE Transactions on Information Theory, vol. 39, No. 4, pp. 1270--1279, July 1993.
|
|
|
|
|
|
[^12]: Christopher Hoobin, Simon J. Puglisi and Justin Zobel, "Relative Lempel-Ziv Factorization for Efficient Storage and Retrieval of Web Collections", Proceedings of the VLDB Endowment, vol. 5, issue 3, pp. 265--273, November 2011.
|
|
|
|
|
|
[^13]: Diego Colombo and Marloes H. Maathuis, "Order-Independent Constraint-Based Causal Structure Learning", Journal of Machine Learning Research, vol. 15, pp. 3921--3962, November 2014 (link).
|
|
|
|