记录中的模式识别

 收藏

你好

我有任务要做我只用一句话简单介绍一下

我有一个20000行的文件。现在的任务是识别相似行的数量。

例1:“敏捷的棕色狐狸跳上了一只懒狗” 例2:“快速的棕色狗跳上一只非常懒惰的狐狸”

我希望将这两句话作为一组。因此,在20000行中,我必须识别出存在多少个组。

时间复杂度是主要问题。请告诉我有什么办法可以继续吗?

回复
  • 大宝剑 回复

    当谈论时间复杂性时,您是否也考虑空间?如果没有,那么您可以尝试...

    /*
    LineDataObject
      - lineNumber (int)
      - content (String[])  // each string is a word of the line
    LineDataComparison
      - lineObj (LineDataObject)
      - duplicatedLineNumber (ArrayList<Integer>)
    LineComparison
      - allLines (ArrayList<LineDataComparison>)
    lineComp <- a LineComparison object
    lineNumber <- 0
    read <- each line of the file starting from the first line
    
    while read!=EOF
      lineNumber <- lineNumber + 1
      aLine <- read the line
      lObj <- create LineDataComparison using the line data (aLine) and lineNumber
      if lObj is not one of lineComp line data
        add lObj to lineComp
      else  // discard the newly created object but add line number instead
        add the line number to the matched LineDataComparison in lineComp
      end if
      read <- next line
    end while
    */
    

    读取文件部分将为O(n)。时间的花费(大O)将取决于10bj与lineComp的比较,因为最坏的情况是O(nlogn * m),其中m是一行中的单词数。空间成本是文件的整个内容(大O),但由于重复,它可能不等于整个文件。一旦找到匹配项就使用break可以提高性能。

  • 小涩先生 回复

    一个想法:为每个新单词分配一个数字,并将代表每个单词的数字保存在该行的数组中。比较数字应该比比较字符串更快。