• Posts
  • RSS
  • ◂◂RSS
  • Contact

  • Quotation Detection

    July 20th, 2012
    algorithms, tech  [html]
    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:

    Randal O’Toole Gets High-Speed Rail Wrong

    Now that there’s decent chance of US investment in rail, Randal O’Toole is resurrecting his takes from the early Obama era, warning that high-speed rail is a multi-trillion dollar money sink. It’s not a good analysis, and in particular it gets the reality…

    via Pedestrian Observations May 12, 2021

    Collections: Teaching Paradox, Europa Universalis IV, Part II: Red Queens

    This is the second part in a series (I) that examines the historical assumptions behind Paradox Interactive’s grand strategy computer game set in the early modern period, Europa Universalis IV (EU4). Last time, we took a look at how EU4 was a game fundame…

    via A Collection of Unmitigated Pedantry May 7, 2021

    Books and websites on babies

    Several people I know are expecting a first baby soon, and I wrote up notes for one of them. Might as well share here too: Medical:Scott Alexander’s Biodeterminist’s Guide to Parenting is an interesting read, and some parts are actionable.  If you live in…

    via The whole sky April 14, 2021

    more     (via openring)


  • Posts
  • RSS
  • ◂◂RSS
  • Contact