Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Algorithms for text fingerprinting?

news.ycombinator.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Ask HN: Algorithms for text fingerprinting?

#11

Post by moyix »

vixsomnis wrote: post #10
moyix wrote: post #9

The relevant search term is "stylometry". One particular paper I remember is from Dawn Song's group at Berkeley a couple years back: http://www.cs.berkeley.edu/~dawnsong/papers/2012%20On%20the%... There'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't know of any open source libraries, for example).

That paper is exactly the sort I was looking for. Thanks. I'm surprised there isn't any open source effort in this area yet (I couldn't find any either). It's just as important as TOR and other anonymity services, since it affects not just passively consuming information, but actively creating it.

If you're interested in defeating stylometry, you should check out Sadia Afroz's PhD thesis as well:

https://www.eecs.berkeley.edu/~sa499/thesis.pdf

Re: Ask HN: Algorithms for text fingerprinting?

#12

Post by thatcat »

Jstylo might be what you're looking for. https://github.com/psal/jstylo

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. https://psal.cs.drexel.edu/index.php/JStylo-Anonymouth

Re: Ask HN: Algorithms for text fingerprinting?

#13

Post by thatcat »

Jstylo might be what you're looking for. https://github.com/psal/jstylo

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. https://psal.cs.drexel.edu/index.php/JStylo-Anonymouth

Re: Ask HN: Algorithms for text fingerprinting?

#14

Post by j42 »

Figured I'd chime in here since I developed an algorithm recently that could be applied to this problem with some basic ML.

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 "similarity" between sets, or, the "Jaccard Index."

If you'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.

If you're looking to build a model to analyze two (or N) text bodies for stylometric similarities, I'd approach the problem in two steps:

1) Minimize the relevant input text.

- Use a bernoulli/categorical distribution to weight words according to uniqueness--NLP and sentiment extraction techniques may also help

- Design a markov process to represent more complex phrasing patterns for the text as a whole

- Filter by a variable threshold to minimize the resulting set of shingles/bins/"interesting nodes" into a computationally-manageable #

2) Use an efficient MinHash intersection to compute a similarity vector (0-1) for the two texts.

I think given the prevalence of training data (I mean, what's more ubiquitous than the written word...) you could probably tune this to a reasonable accuracy and efficient complexity.

Just a 5m thought exercise, but if anyone else has ideas I'd be curious as well :)

Re: Ask HN: Algorithms for text fingerprinting?

#15

Post by pimlottc »

bolomega10000 wrote: post #8

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, "all the words the author uses that commonly surround 'of'" to select on stop word containing common phrases. There is something about the stop word use pattern that makes them har…

What's a "stop word"? Last word in a sentence?

Re: Ask HN: Algorithms for text fingerprinting?

#16

Post by apendleton »

MalcolmDiggs wrote: post #5

When I was in college we turned in papers via "Turnitin" which checked for plagiarism and uniqueness etc. There's an interesting research paper about their algorithms here: https://www.cs.auckland.ac.nz/courses/compsci725s2c/archive/... And if you search for "Turnitin Plagiarism Algorithm" I'm sure you'll find a few more resources.

Plagiarism detection is a somewhat different problem, in that it's looking for specific common text rather than just stylistic choices. Usually it's just looking for high percentages of overlapping ngrams between a test document and documents in a corpus, but two different documents written by the same person wouldn't test positive.

Re: Ask HN: Algorithms for text fingerprinting?

#17

Post by apendleton »

pimlottc wrote: post #15
bolomega10000 wrote: post #8

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, "all the words the author uses that commonly surround 'of'" to select on stop word containing common phrases. There is something about the stop word use pattern that makes them har…

What's a "stop word"? Last word in a sentence?

No, they're usually function words that are in most documents and, at least looking at a document as a bag of words, consequently aren't very analytically useful. Think "the," "of," "and," etc.

Re: Ask HN: Algorithms for text fingerprinting?

#18

Post by amazing_jose »

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 ;)

UPDATE: fix typos.

Re: Ask HN: Algorithms for text fingerprinting?

#19

Post by vixsomnis »

amazing_jose wrote: post #18

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 ;) UPDATE: fix…

Took only a minute to try:

English -> Filipino (Tagalog) -> Chinese-simplified (Mandarin?) -> English

    I remember reading an article about a year ago (NSA) to identify the
    user, based on how they are written, vocabulary, spelling errors,
    grammar, language, and so on.

    It is interesting to me, because it is difficult to change the written
    and spoken word in use. It can be estimated that there are between two
    characters similar amount of help.

    Recently I can think of now is to check plagiarism (used in schools and
    universities, for example) is proprietary algorithm.

    Are there any public this algorithm? I can find out more information?
    (Academic journals?) I just DDGing wrong search terms?
I have to say, this is a great idea. There was some information lost in transit, but most of my thoughts came through (albeit broken). It's probably worse since I used multiple intermediaries and Mandarin doesn't map onto English (or vice-versa) in grammar or vocabulary.

edit: A site for this exists. http://ackuna.com/badtranslator

Post reply on HN