2015 ReconstructingTextualDocumentsf
- (Gallé & Tealdi, 2015) ⇒ Matthias Gallé, and Matías Tealdi. (2015). “Reconstructing Textual Documents from N-grams.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783361
Subject Headings:
Notes
Cited By
- http://scholar.google.com/scholar?q=%222015%22+Reconstructing+Textual+Documents+from+N-grams
- http://dl.acm.org/citation.cfm?id=2783258.2783361&preflayout=flat#citedby
Quotes
Author Keywords
- Code breaking; de bruijn graph; eulerian cycles; graphs and networks; privacy-preserving data mining
Abstract
We analyze the problem of reconstructing documents when we only have access to the n-grams (for n fixed) and their counts from the original documents. Formally, we are interested in recovering the longest contiguous substrings of whose presence in the original documents we are certain. We map this problem on a de Bruijn graph, where the n-grams form the edges and where every Eulerian cycles gives a plausible reconstruction. We define two rules that reduce this graph, preserving all possible reconstructions while at the same time increasing the [[label length}length]] of the edge labels. From a theoretical perspective we prove that the iterative application of these rules gives an irreducible graph equivalent to the original one. We then apply this on the data from the Gutenberg project to measure the number and size of the obtained longest substrings. Moreoever, we analyze how the n-gram corpus could be noised to prevent reconstruction, showing empirically that removing low frequent n-grams has little impact. Instead, we propose another method consisting in adding strategically fictitious n-grams and show that a noised corpus like that is much harder to reconstruct while increasing only little the perplexity of a language model obtained through it.
References
;
Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
---|---|---|---|---|---|---|---|---|---|---|
2015 ReconstructingTextualDocumentsf | Matthias Gallé Matías Tealdi | Reconstructing Textual Documents from N-grams | 10.1145/2783258.2783361 | 2015 |