百度NOIP吧程式設計挑戰賽防作弊系統：基於向量空間法檢查作弊

為了更好的保證比賽的公平性，本次比賽採用基於向量空間法的文字相似比較系統比較程式，可以有效檢查出各類作弊程式。

目前, 在資訊處理方向上, 文字的表示主要採用向量空間模型(VSM)。向量空間模型的基本思想是以向量來表示文字:(W1 , W2 , W3 . . . . . . Wn ), 其中Wi 為第i 個特徵項的權重（詞頻）。詞頻計算方法主要運用 TF-IDF 公式, 目前存在多種 TF-IDF 公式, 我們在系統中採用了一種比較普遍的 TF-IDF 公式:

$$ \text{TF-IDF}(t, d) = \text{TF}(t, d) \times \text{IDF}(t, D) $$

其中，TF(t, d) 是詞頻（Term Frequency），IDF(t, D) 是逆文件頻率（Inverse Document Frequency）。具體的計算公式如下：

$$ \text{TF}(t, d) = \frac{f_{t, d}}{\sum_{t' \in d} f_{t', d}} $$ $$ \text{IDF}(t, D) = \log \frac{N}{|\{d \in D : t \in d\}|} $$

在這裡：

• $f_{t, d}$ 表示詞 t 在文件 d 中的出現次數。
• $\sum_{t' \in d} f_{t', d}$ 表示文件 d 中所有詞的出現次數的總和。
• $N$ 是語料庫中文件的總數。
• $|\{d \in D : t \in d\}|$ 表示包含詞 t 的文件數量。

將這些放在一起，完整的 TF-IDF 公式表示如下：

$$ \text{TF-IDF}(t, d, D) = \frac{f_{t, d}}{\sum_{t' \in d} f_{t', d}} \times \log \frac{N}{|\{d \in D : t \in d\}|} $$

過去的 40 多年中，許多關於資訊檢索的研究工作都是圍繞著 Salton 提出的向量空間法展開的，它也是被廣泛使用的 Smart 系統基礎。在向量空間法中，每個文件被看成一個詞袋，然後被表示成詞條權重的向量：di = (wi1, wi2, …, win)，其中 d 表示一個文件，n 表示詞條空間的維數。每一個詞條的權重代表了該詞條在文件中的重要性。通常我們使用 tf-idf方法或它的一些變形來表示詞條的權重。兩個文件的_相似度_用它們對應向量的夾角的餘弦值來表示。

$$ \cos(\theta) = \frac{\mathbf{A} \cdot \mathbf{B}}{\|\mathbf{A}\| \|\mathbf{B}\|} $$

其中，$\cos(\theta)$ 表示向量 A 和向量 B 之間夾角的餘弦值，$\mathbf{A} \cdot \mathbf{B}$ 表示兩個向量的點積，$\|\mathbf{A}\|$ 和 $\|\mathbf{B}\|$ 分別表示向量 $A$ 和向量 $B$ 的模長。

我寫了一個命令列程式，用來比較任意兩個檔案的相似程度。寫了一個附屬工具程式，用於比較指定目錄下所有的檔案是否存在作弊嫌疑。

希望這能夠在一定程度上緩解作弊情況。

如果你的程式被判為作弊，但你認為沒有作弊，請和我聯絡。此係統只對程式碼不對人。