Ask HN: Algorithms for text fingerprinting?

#1

Post by vixsomnis » Mon, Jun 15, 2015, 12:26 AM UTC

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.

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.

The closest I can think of right now would be the proprietary algorithms used to check for plagiarism (for schools and universities, for instance).

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?

Re: Ask HN: Algorithms for text fingerprinting?

#2

Post by gull » Mon, Jun 15, 2015, 12:58 AM UTC

Check this out: http://www.secretlifeofpronouns.com/exercises.php

Re: Ask HN: Algorithms for text fingerprinting?

#3

Post by vixsomnis » Mon, Jun 15, 2015, 1:10 AM UTC

gull wrote: post #2

Check this out: http://www.secretlifeofpronouns.com/exercises.php

I did the bottle exercise. Very interesting.

I see the term I was looking for was LSM (language style matching). That should help me do more research.

Thanks for the link.

Re: Ask HN: Algorithms for text fingerprinting?

#4

Post by [deleted] » Mon, Jun 15, 2015, 1:35 AM UTC

vixsomnis wrote: post #3

gull wrote: post #2

Check this out: http://www.secretlifeofpronouns.com/exercises.php

I did the bottle exercise. Very interesting. I see the term I was looking for was LSM (language style matching). That should help me do more research. Thanks for the link.

[deleted]

Re: Ask HN: Algorithms for text fingerprinting?

#5

Post by MalcolmDiggs » Mon, Jun 15, 2015, 2:14 AM UTC

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.

Re: Ask HN: Algorithms for text fingerprinting?

#6

Post by gull » Mon, Jun 15, 2015, 2:17 AM UTC

vixsomnis wrote: post #3

gull wrote: post #2

Check this out: http://www.secretlifeofpronouns.com/exercises.php

I did the bottle exercise. Very interesting. I see the term I was looking for was LSM (language style matching). That should help me do more research. Thanks for the link.

Here's a project idea you are free to steal: write a browser plugin that analyzes HN comments and shows up something on the screen. Like "honest", "deceptive", "gratuitously negative".

Brownie points for HN admins if they add text analysis as feedback when we press submit.

I'm tired of signing up with a brand new HN account every few months to cover my tracks after embarrassing myself with less than noble posts.

Re: Ask HN: Algorithms for text fingerprinting?

#7

Post by vixsomnis » Mon, Jun 15, 2015, 2:30 AM UTC

gull wrote: post #6

vixsomnis wrote: post #3

Earlier quoted context omitted.

I did the bottle exercise. Very interesting. I see the term I was looking for was LSM (language style matching). That should help me do more research. Thanks for the link.

Here's a project idea you are free to steal: write a browser plugin that analyzes HN comments and shows up something on the screen. Like "honest", "deceptive", "gratuitously negative". Brownie points for HN admins if they add text analysis as feedback when we press submit. I'm tired of signing up with a brand new HN account every few months to cover my tracks after embarrassing myself with less than noble posts.

I'm less interested in analyzing the meaning of the text than the privacy implications for identification. The way I see it, textual fingerprinting is similar to facial recognition in that it's next to impossible to avoid in public spaces (walking into a subway, using Facebook's app, posting on HN, etc.).

Maybe a style obfuscator. It'd be easier than trying to recognize emotional content.

Re: Ask HN: Algorithms for text fingerprinting?

#8

Post by bolomega10000 » Mon, Jun 15, 2015, 2:45 AM UTC

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 harder to forge.

I've never tried this and I don't know much more about it than that, so I strongly suggest you also find papers that treat authorship attribution by stop words.

Re: Ask HN: Algorithms for text fingerprinting?

#9

Post by moyix » Mon, Jun 15, 2015, 2:49 AM UTC

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

Re: Ask HN: Algorithms for text fingerprinting?

#10

Post by vixsomnis » Mon, Jun 15, 2015, 3:16 AM UTC

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.