<commit_before>.. sidebar:: ToC

    .. contents::

.. _tutorial-datastructures-indices-string-indices:

String Indices
==============

Learning Objective
  You will get an overview of the different kinds of indices in SeqAn and how they are used.

Difficulty
  Average

Duration
  1 h
Prerequisites
  :ref:`tutorial-datastructures-sequences`

Indices in SeqAn
----------------

Indices in SeqAn are substring indices, meaning that they allow efficient pattern queries in strings or sets of strings.
In contrast to, e.g., online-search algorithms that search through the text in :math:`\mathcal{O}(n)`, substring indices find a pattern in sublinear time :math:`o(n)`.

You can find the following indices in SeqAn:

:dox:`IndexSa`
  Suffix Array :cite:`Manber1993`
:dox:`IndexEsa`
  Extended Suffix Array :cite:`Abouelhoda2004`
:dox:`IndexWotd`
  Lazy suffix tree :cite:`Giegerich2003`
:dox:`IndexDfi`
  Deferred Frequency Index :cite:`Weese2008`
:dox:`IndexQGram`
  Q-gram index (see `here <QgramIndex.html>`_)
:dox:`FMIndex`
  Full-text minute index :cite:`Ferragina2001`

Index Construction
------------------

We will now show how we can create the different indices in SeqAn before we show how they are used for pattern search.

All the mentioned indices belong to the generic :dox:`Index` class.
A SeqAn index needs two pieces of information: the type of the :dox:`String` or :dox:`StringSet` to be indexed and the index specialization, such as :dox:`IndexEsa` or :dox:`FMIndex`.

The following code snippet creates an enhanced suffix array index of a string of type :dox:`Dna5`.

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: esa

In contrast, the next code snipped creates a FM index over a set of amino acid sequences:

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: fm

Assignment 1
^^^^^^^^^^^^

.. container:: assignment

   Type
     Review

   Objective
     Copy the code below and

     #. change it to build an :dox:`IndexEsa` over a string of type :dox:`Dna`,
     #. add an :dox:`IndexEsa` over a :dox:`StringSet` of :dox:`String Strings` of type :dox:`Dna`.

     .. includefrags:: demos/tutorial/indices/base.cpp
            :fragment: assignment1

   Solution
     .. container:: foldable

        .. includefrags:: demos/tutorial/indices/assignment_1.cpp

Index Based Pattern Search (Strings)
------------------------------------

SeqAn provides two methods for searching for a pattern in index structures.
One method uses iterators and is similar to traversing search trees or tries.
The tutorial :ref:`tutorial-datastructures-indices-index-iterators` explains this method in more detail.
In this section you will learn how to find a pattern with the :dox:`Finder` interface.

The :dox:`Finder` is an object that stores all necessary information for searching for a pattern using an index.
The following line of code shows how the :dox:`Finder` is initialized.

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: finder

After initialization it is possible to use the :dox:`Finder#find` function in order to trigger a search for all occurrences of a given pattern in the underlying :dox:`String` or :dox:`StringSet`.
In this example, we search for the pattern ``ACGT``:

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: finder2

Calling the function :dox:`Finder#find` invokes the localization of all occurrences of a given pattern.
It works by modifying pointers of the ``Finder`` to tables of the index.
For example, the :dox:`Finder` of ``esaIndex`` stores two pointers, pointing to the first and last suffix array entry that stores an occurrence of the pattern.

The return value of the :dox:`Finder#find` function tells us whether or not a given pattern occurs in the text.
Furthermore, if there are several instances of a pattern, consecutive calls of :dox:`Finder#find` will modify the :dox:`Finder` such that it points to the next occurrence after each call:

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: finder_multiple

The above code is not very useful, since we do not know the locations of the first, second or third pattern occurrence.
The function :dox:`Finder#position` will help here.
:dox:`Finder#position` called on a finder returns the location of the ``x``\ th pattern, where ``x`` can be the first, second, or any other occurrence of the pattern.

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: finder_position

.. tip::

   Indices in SeqAn are build on demand.
   That means that the index tables are not build when the constructor is called, but when we search for a pattern for the first time.

Assignment 2
^^^^^^^^^^^^

.. container:: assignment

   Type
     Application

   Objective
     Write a small program that prints the locations of all occurrences of ``"TATAA"`` in ``"TTATTAAGCGTATAGCCCTATAAATATAA"``.

   Hints
    Use the :dox:`Finder#find` function as the conditional instruction of a <tt>while</tt> loop.<commit_msg>[DOC] Removed indexed based pattern search from DataStructures-Tutorial<commit_after>.. sidebar:: ToC

    .. contents::

.. _tutorial-datastructures-indices-string-indices:

String Indices
==============

Learning Objective
  You will get an overview of the different kinds of indices in SeqAn and how they are used.

Difficulty
  Average

Duration
  1 h
Prerequisites
  :ref:`tutorial-datastructures-sequences`

Indices in SeqAn
----------------

Indices in SeqAn are substring indices, meaning that they allow efficient pattern queries in strings or sets of strings.
In contrast to, e.g., online-search algorithms that search through the text in :math:`\mathcal{O}(n)`, substring indices find a pattern in sublinear time :math:`o(n)`.

You can find the following indices in SeqAn:

:dox:`IndexSa`
  Suffix Array :cite:`Manber1993`
:dox:`IndexEsa`
  Extended Suffix Array :cite:`Abouelhoda2004`
:dox:`IndexWotd`
  Lazy suffix tree :cite:`Giegerich2003`
:dox:`IndexDfi`
  Deferred Frequency Index :cite:`Weese2008`
:dox:`IndexQGram`
  Q-gram index (see `here <QgramIndex.html>`_)
:dox:`FMIndex`
  Full-text minute index :cite:`Ferragina2001`

Index Construction
------------------

We will now show how we can create the different indices in SeqAn before we show how they are used for pattern search.

All the mentioned indices belong to the generic :dox:`Index` class.
A SeqAn index needs two pieces of information: the type of the :dox:`String` or :dox:`StringSet` to be indexed and the index specialization, such as :dox:`IndexEsa` or :dox:`FMIndex`.

The following code snippet creates an enhanced suffix array index of a string of type :dox:`Dna5`.

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: esa

In contrast, the next code snipped creates a FM index over a set of amino acid sequences:

.. includefrags:: demos/tutorial/indices/base.cpp
      :fragment: fm

Assignment 1
^^^^^^^^^^^^

.. container:: assignment

   Type
     Review

   Objective
     Copy the code below and

     #. change it to build an :dox:`IndexEsa` over a string of type :dox:`Dna`,
     #. add an :dox:`IndexEsa` over a :dox:`StringSet` of :dox:`String Strings` of type :dox:`Dna`.

     .. includefrags:: demos/tutorial/indices/base.cpp
            :fragment: assignment1

   Solution
     .. container:: foldable

        .. includefrags:: demos/tutorial/indices/assignment_1.cpp

Assignment 2
^^^^^^^^^^^^

.. container:: assignment

   Type
     Application

   Objective
     Write a small program that prints the locations of all occurrences of ``"TATAA"`` in ``"TTATTAAGCGTATAGCCCTATAAATATAA"``.

   Hints
    Use the :dox:`Finder#find` function as the conditional instruction of a <tt>while</tt> loop.
{'fraction_non_alphanumeric': 0.10668913663469018, 'fraction_numerical': 0.006870624837956961, 'mean_word_length': 3.879822896900696, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4440672', 'n_tokens_mistral': 2343, 'n_tokens_neox': 2231, 'n_words': 928}