The documents were approximately 30 KB of size, the smallest were 18 KB and the largest were 44 KB.
We have used methods which are applicable in general to any type of text input with no apriori information about the input document.
-All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
-according to their priority. After each executed query the intermediate results of plagiarism
-were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
-This process leads to continuing lowering the number of executed queries, for more details see the following passages.
+%All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
+%according to their priority. After each executed query the intermediate results of plagiarism
+%were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
+%This process leads to continuing lowering the number of executed queries, for more details see the following passages.
We can divide constructed queries into three main groups according to their origin:
Thus we firstly filter out stop words according to general English stop words list.
Secondly we used reference corpus word list as an additional filter.
We used words in their simple verbatim occurrence allied to a
-statistical estimate of likelihood. As a result of this a word to become a key
+statistical estimate of likelihood. As a result of this, a word to become a key
must not exists in the stop list and must occur in the suspicious document relatively much more frequently
than in the reference corpus. We used a corpus created from common English web sources, which contains
more then 4 billion tokens~\cite{ententen}.
-The statistical measure TF-IDF was applied in order to decide whether the processed word shall become a keyword.
+The statistical measure TF-IDF~\cite{Introduction_to_information_retrieval}
+was applied in order to decide whether the processed word shall become a keyword.
The TF-IDF combines term frequency (TF) and inverse document frequency (IDF) to produce composite weight of a given term.
Taking into account the average length of the suspicious document and minimizing the number of used queries we set TF-IDF weight threshold to 0.02,
which resulted in about 10 to 20 terms identified as keywords per document.
largest change of AWFC compared to AWFC of their neighbouring previous window were selected as candidate for query extraction.
-The query from the representative sentence were composed by 6 words from the sentence beginning, also omitting stop words.
+The query from the representative sentence was composed by 6 words from the sentence beginning, also omitting stop words.
We chose 6 words to cover higher portion of selected sentence and not to exceed
the phrasal ChatNoir query limit.
This type of query is actually looking for documents containing the very same or at least the very similar sentence,
The intrinsic plagiarism based queries are document positionable, meaning that we can store
their position within the document. It is due to the fact, that
-those queries are created from more or less subsequent words. As a result of that they are also executed conditionally, for more
+those queries are created from more or less subsequent words. As a result, they are also executed conditionally, for more
information see section~\ref{process}.
The position within the document were set to the
start position of the representative sentence.
They characterize only a specific portion of the suspicious document on the contrary to keyword based queries.
\subsection{Headers based queries}
-The last type of queries are queries constructed from local headers of document.
-The header usually characterize briefly and accurately following section, thus it
-can be used as a search query. We considered headers only from 2 to 6 words in length.
+The last type of queries were constructed from local headers of the document.
+A header usually characterize briefly and accurately the following section, thus it
+can be used as a search query. In real scenarios the headers should
+be located using some document metadata, in that way we can distinguish for example more header levels.
+In the case of PAN 12 competition we have detected headers according to several
+basic rules. Those basic rules applied on most headers from given test corpus text files.
+As a header is considered any line which has an empty line above and bellow the actual line
+and is from 2 to 6 words in length also omitting stop words.
+Note that length of header based queries are variable, thus they can be both specific
+and general according to their length. They are also document positionable.
+We calculated their position as start position of the following text.
-\subsection{Input document processing}~\label{process}
+\subsection{Combining and executing queries}~\label{process}
-\subsection{Queries comparison}
+After each executed query the intermediate results of plagiarism
+were calculated using the multi feature document comparison techniques described in section~\ref{yenya}.
+This process leads to continuing lowering the number of executed queries, for more details see the following passages.
+
+All queries from a given document were firstly preconstructed and they were afterwards sequentially executed
+according to their priority.
+The first all keyword based queries, the second
+intrinsic plagiarism based and the last headers based, whilst we could omit some of the positionable queries during the process,
+which is described further in this section.
+The queries processing is outlined as Algorithm~\ref{alg:queries}, where for simplicity the snippet calculation and a web source download is omitted.
+After executing a query the intermediate results were always
+calculated as follows: For every query result in result page based
+on a snippet to input suspicious document similarities, we decided whether to actually
+download the resulting URL or not. Since the snippet contains portions of Web document to each
+given keyword, we calculated pre-similarity as apportionment of every word match between the snipped and the suspicious document.
+If there were at least 80\% match, we downloaded the web source for thorough investigation.
+For each downloaded web document we calculated similarities with the input suspicious document
+in the same way as described in section~\ref{yenya}. All similarities has been stored in form of intervals from within
+the input suspicious document. In other words for every similar part between the downloaded
+document and the suspicious document we stored the beginning position and the ending position of that part in
+the suspicious document.
+
+As a result of that, we can during processing further queries, which haven't been executed yet, omit those
+of which document position intersects with any of already found similarities intervals. This procedure
+leads us to lowering the total number of executed queries.
+All downloaded documents, which have at least one similarity interval, are declared
+as possible source of the plagiarism.
+
+
+\renewcommand{\algorithmicrequire}{\textbf{Input:}}
+\renewcommand{\algorithmicensure}{\textbf{Output:}}
+
+
+\algsetup{indent=2em}
+\begin{algorithm}[h!]
+\caption{Queries execution}\label{alg:queries}
+\begin{algorithmic}[1]
+\REQUIRE suspicious document $d$, queries $Q_{KW}, Q_{Intrinsic}, Q_{Headers}$
+%keyword, intrinsic and headers based queries $Q_{KW}, Q_{Intrinsic}, Q_{Headers}$,
+
+\ENSURE plagiarism source candidate web documents $W_{plag}$
+\medskip
+
+\STATE $I \leftarrow \emptyset; I \in \mathbb{N}^2$
+\STATE $W \leftarrow \emptyset$
+
+\FORALL{$q \in (Q_{KW} \cup Q_{Intrinsic} \cup Q_{Headers}) $}
+ \IF{$position(q)$ do not intersects with any interval $ \vec{i} \in I$}
+ \STATE $W \leftarrow execute(q)$
+ \FORALL{$w \in W$}
+ \STATE $I_{sub} \leftarrow get\_similarities(w, d)$ %\COMMENT{output is set of intervals similarities $[d_{start},d_{end}]$}
+ \STATE $I \leftarrow I \cup I_{sub}$
+ \IF{$I_{sub} \neq \emptyset$}
+ \STATE $W_{plag} \leftarrow W_{plag} \cup \{w\}$
+ \ENDIF
+ \ENDFOR
+ \ENDIF
+\ENDFOR
+\RETURN $W_{plag}$
+
+\end{algorithmic}
+\end{algorithm}
+
+\subsection{Queries comparison}
+During the test phase there were extracted 133 keywords based queries, 165 intrinsic plagiarism
+based queries and 331 headers based queries in total. Table~\ref{querycount} shows the arithmetic mean
+of the query count per document. We can see that nearly half of the prepared queries were
+omitted due to the fact, that there had been found a similarity including their document position.
+
+\begin{center}
+\begin{table}[h]
+\begin{center}
+\caption{\footnotesize The arithmetic mean of the query count and the omitted query count per document}
+\vspace{0.3 cm}
+\begin{tabular}{|c|c|c|}
+\hline
+\label{querycount}
+{\bf Query type} & {\bf Extracted}& {\bf Omitted} \\ \hline \hline
+KW & 4.16 & N/A \\ \hline
+Intrinsic & 5.16 & 2.35 \\ \hline
+Headers & 10.34 & 4.75 \\ \hline
+\end{tabular}\\
+\end{center}
+\end{table}
+\end{center}
+
+
+\begin{center}
+\begin{table}[h]
+\begin{center}
+\caption{\footnotesize The total portion of similarities found, taking into account number of similarities regardless of interval sizes.}
+\vspace{0.3 cm}
+\begin{tabular}{|c|c|}
+\hline
+\label{querySuccess}
+{\bf Query type} & {\bf Similarities portion } \\ \hline \hline
+KW & 72.5 \% \\ \hline
+Intrinsic & 24.3 \% \\ \hline
+Headers & 10.34 \% \\ \hline
+\end{tabular}\\
+\end{center}
+\end{table}
+\end{center}
https://www.fi.muni.cz/~kas/git / pan12-paper.git / blobdiff