Quotation Detection

July 20th, 2012
algorithms, tech
I want to thread comments: when a comment quotes another comment it's probably a reply, so attach them together to make the conversation clearer. This means figuring out which comments quote which other comments. I tried a brute force way:
  for each comment A:
    for each later comment B:
      for each word X in A:
        for each word Y in B:
          do A and B match for N words starting at X and Y?
This is psuedocode for an O(n^2*m^2) solution. Not so good. I coded it up in javascript and while I think it's fast enough in Chrome, Firefox, and even my phone, it took IE8 nearly a minute. While I could probably run this on my server and do fine with some combination of caching and C, it seems inefficient. Is there a better algorithm? What is the general version of this problem called?

Update 2012-07-21: Several commenters suggested a better algorithm: to find all quotes of length N, build a dictionary from all sequences of N words to a list of comments in which they appeared. This is O(n*m) and running it it's much faster. I tested it in IE8, and it loaded quickly instead of freezing the browser. I thought briefly about doing something like this earlier, but wrote it off as using insane amounts of memory. After more people suggested it, I realized it only uses N times as much memory as just storing the comments.

Comment via: google plus, facebook

Recent posts on blogs I like:

A Big Problem With The Going To Bed Book

One day my dad was reading this book called the "Going to Bed Book" to my sister Nora. The book is basically about a bunch of animals who are getting ready for bed on a boat. They go down the stairs, take a bath, hang their towels on the wall, find…

via Lily Wise's Blog Posts September 18, 2023

Investing in boundaries with young kids

Putting in some work to get the behavior you want The post Investing in boundaries with young kids appeared first on Otherwise.

via Otherwise August 15, 2023

Self-driving car bets

This month I lost a bunch of bets. Back in early 2016 I bet at even odds that self-driving ride sharing would be available in 10 US cities by July 2023. Then I made similar bets a dozen times because everyone disagreed with me. The first deployment to pot…

via The sideways view July 29, 2023

more     (via openring)