• Posts
  • RSS
  • ◂◂RSS
  • Contact

  • 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:

    Corncob Dolls

    I went to a farm and at the farm I got to see a corncrib and the corn that had fell out of the corncrib that no one wanted I got to use my fingers to take off the corn kernels and once the cobs were empty I put them in a bag and then once I got back to the…

    via Anna Wise's Blog Posts November 7, 2022

    Light Switch

    When I got my loft bed it was just so annoying every morning to have to get out of bed, climb down the ladder, turn the light on, and climb back up, just so I could see stuff. I decided to make a string for my light switch because I really wanted to be abl…

    via Lily Wise's Blog Posts November 7, 2022

    Childbirth location and safety

    How much does it matter for you and for the baby? The post Childbirth location and safety appeared first on Otherwise.

    via Otherwise November 6, 2022

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact