TextRank算法时空复杂度求解：基于指定EMNLP2004论文的技术问询

Great question! Let's break down the time and space complexity of TextRank for both keyword extraction and sentence summarization, building on your initial reasoning about PageRank's complexity:

Keyword Extraction #

• Time Complexity: Your initial conclusion of O(i*(n+m)) is spot-on. Here, n is the number of vocabulary nodes, m is the number of co-occurrence edges between words, and i is the number of PageRank iterations needed for convergence (typically between 10-50, a constant in practice). Since i doesn't scale with input size, you could also approximate this as O(n+m) for practical purposes.
• Space Complexity: If using an adjacency matrix to represent the word co-occurrence graph, the space cost is O(V²) where V is the size of the vocabulary. However, if you use an adjacency table (a more memory-efficient structure for sparse graphs), this drops to O(n+m) since you only store existing edges rather than all possible pairs.

Sentence Extraction (Summarization) #

The core PageRank iteration logic stays the same, but the graph nodes and edge calculation add some key nuances:

• Time Complexity:
  1. Graph Construction: First, you need to compute similarity scores between every pair of sentences (often using cosine similarity on word embeddings or bag-of-words vectors). This step takes O(S²*d) where S is the number of sentences and d is the dimensionality of the sentence vectors.
  2. PageRank Iterations: Just like keyword extraction, each iteration runs in O(S+E) time where E is the number of edges between sentences (if you keep only edges above a similarity threshold, E may be smaller than S²). Multiply by i iterations, giving O(i*(S+E)).
  3. Total Time: Combining both steps, the overall time complexity is O(S²*d + i*(S+E)).
• Space Complexity:
  • Using an adjacency matrix for sentence similarity: O(S²) where S is the number of sentences.
  • Using an adjacency table: O(S+E) to store only valid edges between similar sentences.

It's worth noting that in real-world implementations, optimizations (like pruning low-similarity edges early) can reduce both time and space costs significantly, especially for large document collections.

内容的提问来源于stack exchange，提问作者johnbumble