TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

Ask HN: Algorithms for text fingerprinting?

92 pointsby vixsomnisalmost 10 years ago
I remember reading an article a year or so ago about (the NSA) identifying users based on how they write: vocabulary, spelling mistakes, grammar, dialect, and so on.<p>This is interesting to me because it is extremely difficult to change the vocabulary I use in writing and speaking. Being able to estimate the amount of similarity between two pieces of text would be useful.<p>The closest I can think of right now would be the proprietary algorithms used to check for plagiarism (for schools and universities, for instance).<p>Are there any publicly available algorithms for this? Where can I go to learn more? (Academic journals?) Am I just DDGing the wrong search terms?

17 comments

j42almost 10 years ago
Figured I&#x27;d chime in here since I developed an algorithm recently that could be applied to this problem with some basic ML.<p>Basically the first step would be shingling the text (choosing a sampling domain) and generating a MinHash struct (computationally cheap) which can then be used to find the &quot;similarity&quot; between sets, or, the &quot;Jaccard Index.&quot;<p>If you&#x27;re clever about this, you can use HyperLogLogs to encode these MinHash structs gaining a great deal of speed with a marginal error rate, all while allowing for arbitrary N-levels of intersection.<p>If you&#x27;re looking to build a model to analyze two (or N) text bodies for stylometric similarities, I&#x27;d approach the problem in two steps:<p>1) Minimize the relevant input text.<p>- Use a bernoulli&#x2F;categorical distribution to weight words according to uniqueness--NLP and sentiment extraction techniques may also help<p>- Design a markov process to represent more complex phrasing patterns for the text as a whole<p>- Filter by a variable threshold to minimize the resulting set of shingles&#x2F;bins&#x2F;&quot;interesting nodes&quot; into a computationally-manageable #<p>2) Use an efficient MinHash intersection to compute a similarity vector (0-1) for the two texts.<p>I think given the prevalence of training data (I mean, what&#x27;s more ubiquitous than the written word...) you could probably tune this to a reasonable accuracy and efficient complexity.<p>Just a 5m thought exercise, but if anyone else has ideas I&#x27;d be curious as well :)
评论 #9718616 未加载
moyixalmost 10 years ago
The relevant search term is &quot;stylometry&quot;. One particular paper I remember is from Dawn Song&#x27;s group at Berkeley a couple years back:<p><a href="http:&#x2F;&#x2F;www.cs.berkeley.edu&#x2F;~dawnsong&#x2F;papers&#x2F;2012%20On%20the%20Feasibility%20of%20Internet-Scale%20Author%20Identification.pdf" rel="nofollow">http:&#x2F;&#x2F;www.cs.berkeley.edu&#x2F;~dawnsong&#x2F;papers&#x2F;2012%20On%20the%...</a><p>There&#x27;s a lot of public work on the topic, but it looks like right now the best place to look is still in academic papers (I don&#x27;t know of any open source libraries, for example).
评论 #9718534 未加载
评论 #9718812 未加载
评论 #9717324 未加载
评论 #9718349 未加载
thatcatalmost 10 years ago
Jstylo might be what you&#x27;re looking for. <a href="https:&#x2F;&#x2F;github.com&#x2F;psal&#x2F;jstylo" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;psal&#x2F;jstylo</a><p>The same group also has created a text obfuscation tool called anonymouth that helps you obfuscate your word choices, but it has still yet to be released. <a href="https:&#x2F;&#x2F;psal.cs.drexel.edu&#x2F;index.php&#x2F;JStylo-Anonymouth" rel="nofollow">https:&#x2F;&#x2F;psal.cs.drexel.edu&#x2F;index.php&#x2F;JStylo-Anonymouth</a>
benten10almost 10 years ago
I may be late to the party, but finally my time to shine! As has been mentioned earlier, the field gou are looking for is called stylometry, and has almost a century of history behind it, and also the field if my thesis. After looking at what everyone has been saying, I just felt like copying and pasting my 20 page literature review here, but I&#x27;d recommend you look at narayanan at all (2012) paper (internet scale authorship attribution). The algorithm it uses is not particularly complex and would take you a week, tops, to implement if you put in a few hours a day, and that&#x27;s including doing all the related research and catching up with the linear algebra involved if you need to.
gnuralmost 10 years ago
I&#x27;ve started a simular project myself recently, I check on various parameters (reading level score, words per sentence, syllables per word, sentences per paragraph, average word length, average syllable count) and calculate the distance between 2 texts &#x2F; authors using a simple euclidean distance.<p>I started out with the code provided on <a href="https:&#x2F;&#x2F;github.com&#x2F;mac389&#x2F;ToxTweet&#x2F;blob&#x2F;master&#x2F;textanalyzer.py" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;mac389&#x2F;ToxTweet&#x2F;blob&#x2F;master&#x2F;textanalyzer....</a> I use it in a private project, but the results are promising!
pdpdalmost 10 years ago
I wonder if this is how the authors of Truecrypt where identified. I remember reading something similar about this in regards to coding style.<p>I am sure the Truecrypt authors contributed to more than one project.
MalcolmDiggsalmost 10 years ago
When I was in college we turned in papers via &quot;Turnitin&quot; which checked for plagiarism and uniqueness etc.<p>There&#x27;s an interesting research paper about their algorithms here: <a href="https:&#x2F;&#x2F;www.cs.auckland.ac.nz&#x2F;courses&#x2F;compsci725s2c&#x2F;archive&#x2F;termpapers&#x2F;jrotzky.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.auckland.ac.nz&#x2F;courses&#x2F;compsci725s2c&#x2F;archive&#x2F;...</a><p>And if you search for &quot;Turnitin Plagiarism Algorithm&quot; I&#x27;m sure you&#x27;ll find a few more resources.
评论 #9717671 未加载
nodelessnessalmost 10 years ago
This one time JK Rowling was found out writing by a pseudonym[1] using this program:<p><a href="http:&#x2F;&#x2F;evllabs.com&#x2F;jgaap&#x2F;w&#x2F;index.php&#x2F;Main_Page" rel="nofollow">http:&#x2F;&#x2F;evllabs.com&#x2F;jgaap&#x2F;w&#x2F;index.php&#x2F;Main_Page</a><p>[1] <a href="http:&#x2F;&#x2F;blogs.wsj.com&#x2F;speakeasy&#x2F;2013&#x2F;07&#x2F;16&#x2F;the-science-that-uncovered-j-k-rowlings-literary-hocus-pocus&#x2F;" rel="nofollow">http:&#x2F;&#x2F;blogs.wsj.com&#x2F;speakeasy&#x2F;2013&#x2F;07&#x2F;16&#x2F;the-science-that-u...</a>
评论 #9718118 未加载
MasterScratalmost 10 years ago
JGAAP is pretty awesome, it has both Java API and GUI: <a href="https:&#x2F;&#x2F;github.com&#x2F;evllabs&#x2F;JGAAP" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;evllabs&#x2F;JGAAP</a><p>JStylo that was already mentioned is based on JGAAP. You have some more here: <a href="http:&#x2F;&#x2F;evllabs.com&#x2F;jgaap&#x2F;w&#x2F;index.php&#x2F;FAQ#What_other_tools_are_out_there.3F" rel="nofollow">http:&#x2F;&#x2F;evllabs.com&#x2F;jgaap&#x2F;w&#x2F;index.php&#x2F;FAQ#What_other_tools_ar...</a>
gullalmost 10 years ago
Check this out: <a href="http:&#x2F;&#x2F;www.secretlifeofpronouns.com&#x2F;exercises.php" rel="nofollow">http:&#x2F;&#x2F;www.secretlifeofpronouns.com&#x2F;exercises.php</a>
评论 #9716961 未加载
amazing_josealmost 10 years ago
The results could be horrible, but can imagine a simple technique for hiding all those clues. Just send the text to google translate, translate it to an intermediate language and the back to the original one. I can warranty an excellent t rinse and clean. Change the intermediate language and you will change the features of the final text. Of course, you risk horrible semantic changes in the final text ;)<p>UPDATE: fix typos.
评论 #9717975 未加载
评论 #9717755 未加载
CSDudealmost 10 years ago
There is a public domain fingerprinting tool, that is used in MOSS (Measure Of Software Similarity). You can get the ideas from there.<p><a href="http:&#x2F;&#x2F;theory.stanford.edu&#x2F;~aiken&#x2F;publications&#x2F;papers&#x2F;sigmod03.pdf" rel="nofollow">http:&#x2F;&#x2F;theory.stanford.edu&#x2F;~aiken&#x2F;publications&#x2F;papers&#x2F;sigmod...</a>
bolomega10000almost 10 years ago
A simple one is based on analysing stop words. I guess you could do vector similarity of stop word relative frequency. You could try additional features such as word bigrams and trigrams and contain stop words. In other words, things like, &quot;all the words the author uses that commonly surround &#x27;of&#x27;&quot; to select on stop word containing common phrases.<p>There is something about the stop word use pattern that makes them harder to forge.<p>I&#x27;ve never tried this and I don&#x27;t know much more about it than that, so I strongly suggest you also find papers that treat authorship attribution by stop words.
评论 #9717618 未加载
fauxfauxpasalmost 10 years ago
somewhat related - excerpt from Cryptonomicon - The percussionist stands up. &quot;Every radio operator has a distinctive style of keying—we call it his fist. With a bit of practice, our Y Service people can recognize different German operators by their fists—we can tell when one of them has been transferred to a different unit, for example.&quot;<p>and this article by Schneier - Identifying People By Their Writing Style - <a href="https:&#x2F;&#x2F;www.schneier.com&#x2F;blog&#x2F;archives&#x2F;2011&#x2F;08&#x2F;identifying_peo_2.html" rel="nofollow">https:&#x2F;&#x2F;www.schneier.com&#x2F;blog&#x2F;archives&#x2F;2011&#x2F;08&#x2F;identifying_p...</a>
banealmost 10 years ago
Here&#x27;s a quick one:<p>1) tokenize each text into a different bag(set) of words.<p>2) Compute the Jaccard index[1] using the two sets.<p>Here&#x27;s another<p>1) tokenize each text into a multi-bag(set) of words, keeping track of token frequency<p>2) keeping the token frequency, order the sets into lists<p>3) map the lists of words onto an n-dimensional space (where n is say...all of the words into the two documents) as vectors<p>4) compute the cosine similarity [2]<p>Here&#x27;s another:<p>1) tokenize the texts into two bags of words<p>2) compute the set difference going both ways.<p>3) does either difference contain discriminator tokens that rule it out as being from that person<p>4 (optional)): extend to 2-3-n-grams<p>Here&#x27;s another (a variant of the one above):<p>1) compute 1-2-3-n-grams from one of the texts<p>2) insert the n-grams into a set<p>3) compute the same for the second document and test for set membership<p>4) compute the number of total n-grams from your second document<p>5) compute (non-in-set&#x2F;total-n-grams) * 100 to yield a &quot;uniqueness&quot; measure<p>6) determine if the second document is &quot;unique&quot; enough<p>And another:<p>1) assuming you have a sample corpus from a writer and want to know if a new text belongs in that corpus<p>2) follow the method above but for step #1 and 2 do it with the entire reference corpus<p>And another:<p>1) produce an ontology of discriminator terms and categories unique to the writer<p>2) use an (named entity recognition) NER tool of some kind to find those terms in each document<p>3) use the set of found terms as an alternative to a bag of words for the Jaccard or Vector models above<p>You may need to play with stopword list removal, tokenization schemes and n-gram windows (for example, omitting 1-grams might focus the analysis on phrase usage vs. vocabulary usage)<p>1 - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Jaccard_index" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Jaccard_index</a><p>2 - <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cosine_similarity" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Cosine_similarity</a>
评论 #9718751 未加载
espealmost 10 years ago
afaik, stylo (<a href="https:&#x2F;&#x2F;sites.google.com&#x2F;site&#x2F;computationalstylistics&#x2F;stylo" rel="nofollow">https:&#x2F;&#x2F;sites.google.com&#x2F;site&#x2F;computationalstylistics&#x2F;stylo</a>) is the academic go-to solution. it is even sporting a gui
wodenokotoalmost 10 years ago
You want to look for &#x27;author attribution&#x27; as your keyword.<p>There are 2 main ways for assessing author attribution. One is through stylistic markers, where you look for a set of predefined features. The is average length per paragraph, or the number of times &#x27;whenever&#x27; is used. This is highly language dependant.<p>The other way is through character n-gram analysis. You chose for which N you want to harvest N-grams and your author profile is the frequency of top 2000 n-grams and you compare this profile with a documents top 2000 n-grams and the profile with the shortest distance is your match.<p>Robert Layton has a tutorial and some code on N-gram attribution on Github:<p>* <a href="https:&#x2F;&#x2F;github.com&#x2F;robertlayton&#x2F;authorship_tutorials" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;robertlayton&#x2F;authorship_tutorials</a><p>* <a href="https:&#x2F;&#x2F;github.com&#x2F;robertlayton&#x2F;author-detection" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;robertlayton&#x2F;author-detection</a><p>And here&#x27;s a list of papers I&#x27;ve reviewed while doing a similar project.<p>[1] Shlomo Argamon, Moshe Koppel, Jonathan Fine, and Anat Rachel Shimoni. Gender, genre, and<p>writing style in formal written texts.<p>23(3):321–346, 2003.<p>[2] John F Burrows. ‘an ocean where each kind...’: Statistical analysis and some major determinants<p>of literary style. Computers and the Humanities, 23(4-5):309–321, 1989.<p>[3] Georgia Frantzeskou, Efstathios Stamatatos, Stefanos Gritzalis, and Sokratis Katsikas. Source<p>code author identification based on n-gram author profiles. In Artificial Intelligence Applica- tions and Innovations, pages 508–515. Springer, 2006.<p>[4] Sheena Gardner and Hilary Nesi. A classification of genre families in university student writing.<p>Applied linguistics, 34(1):25–52, 2013.<p>[6] John Houvardas and Efstathios Stamatatos. N-gram feature selection for authorship identifica- tion. In Artificial Intelligence: Methodology, Systems, and Applications, pages 77–86. Springer,<p>2006.<p>[7] Patrick Juola. Authorship attribution. Foundations and Trends in information Retrieval,<p>1(3):233–334, 2006.<p>[8] Vlado Kešelj, Fuchun Peng, Nick Cercone, and Calvin Thomas. N-gram-based author profiles<p>for authorship attribution. In Proceedings of the conference pacific association for computational<p>linguistics, PACLING, volume 3, pages 255–264, 2003.<p>[9] Maarten Lambers and Cor J Veenman. Forensic authorship attribution using compression dis- tances to prototypes. In Computational Forensics, pages 13–24. Springer, 2009.<p>[11] Fiona J Tweedie and R Harald Baayen. How variable may a constant be? measures of lexical<p>richness in perspective. Computers and the Humanities, 32(5):323–352, 1998.<p>[12] Cor J Veenman and Zhenshi Li. Authorship verification with compression features.<p>[13] Rong Zheng, Jiexun Li, Hsinchun Chen, and Zan Huang. A framework for authorship identifi-<p>cation of online messages: Writing-style features and classification techniques. Journal of the<p>American Society for Information Science and Technology, 57(3):378–393, 2006.