Add Inverted Index (TheAlgorithms#262)

Leefrost · web-flow · commit f7c5b60b88a3 · 2021-10-21T07:49:47.000+03:00
diff --git a/DataStructures.Tests/InvertedIndexTests.cs b/DataStructures.Tests/InvertedIndexTests.cs
@@ -0,0 +1,37 @@
+﻿using System.Collections.Generic;
+using FluentAssertions;
+using NUnit.Framework;
+
+namespace DataStructures.Tests
+{
+    public class InvertedIndexTests
+    {
+        [Test]
+        public void Or_GetSourcesWithAtLeastOneFromList_ReturnAllSources()
+        {
+            var index = new InvertedIndex();
+            var source1 = "one star is sparkling bright";
+            var source2 = "two stars are sparkling even brighter";
+            index.AddToIndex(nameof(source1), source1);
+            index.AddToIndex(nameof(source2), source2);
+
+            var or = index.Or(new List<string> { "star", "sparkling" });
+
+            or.Should().BeEquivalentTo(nameof(source1), nameof(source2));
+        }
+
+        [Test]
+        public void And_GetSourcesWithAllInsideList_ReturnFirstSource()
+        {
+            var index = new InvertedIndex();
+            var source1 = "one star is sparkling bright";
+            var source2 = "two stars are sparkling even brighter";
+            index.AddToIndex(nameof(source1), source1);
+            index.AddToIndex(nameof(source2), source2);
+
+            var and = index.And(new List<string> { "star", "sparkling" });
+
+            and.Should().BeEquivalentTo(nameof(source1));
+        }
+    }
+}
diff --git a/DataStructures/InvertedIndex.cs b/DataStructures/InvertedIndex.cs
@@ -0,0 +1,82 @@
+﻿using System.Collections.Generic;
+using System.Linq;
+
+namespace DataStructures
+{
+    /// <summary>
+    /// Inverted index is the simplest form of document indexing,
+    /// allowing performing boolean queries on text data.
+    ///
+    /// This realization is just simplified for better understanding the process of indexing
+    /// and working on straightforward string inputs.
+    /// </summary>
+    public class InvertedIndex
+    {
+        private readonly Dictionary<string, List<string>> invertedIndex = new();
+
+        /// <summary>
+        /// Build inverted index with source name and source content.
+        /// </summary>
+        /// <param name="sourceName">Name of the source.</param>
+        /// <param name="sourceContent">Content of the source.</param>
+        public void AddToIndex(string sourceName, string sourceContent)
+        {
+            var context = sourceContent.Split(' ').Distinct();
+            foreach (var word in context)
+            {
+                if (!invertedIndex.ContainsKey(word))
+                {
+                    invertedIndex.Add(word, new List<string> { sourceName });
+                }
+                else
+                {
+                    invertedIndex[word].Add(sourceName);
+                }
+            }
+        }
+
+        /// <summary>
+        /// Returns the source names contains ALL terms inside at same time.
+        /// </summary>
+        /// <param name="terms">List of terms.</param>
+        /// <returns>Source names.</returns>
+        public IEnumerable<string> And(IEnumerable<string> terms)
+        {
+            var entries = terms
+                .Select(term => invertedIndex
+                    .Where(x => x.Key.Equals(term))
+                    .SelectMany(x => x.Value))
+                .ToList();
+
+            var intersection = entries
+                .Skip(1)
+                .Aggregate(new HashSet<string>(entries.First()), (hashSet, enumerable) =>
+                {
+                    hashSet.IntersectWith(enumerable);
+                    return hashSet;
+                });
+
+            return intersection;
+        }
+
+        /// <summary>
+        /// Returns the source names contains AT LEAST ONE from terms inside.
+        /// </summary>
+        /// <param name="terms">List of terms.</param>
+        /// <returns>Source names.</returns>
+        public IEnumerable<string> Or(IEnumerable<string> terms)
+        {
+            var sources = new List<string>();
+            foreach (var term in terms)
+            {
+                var source = invertedIndex
+                    .Where(x => x.Key.Equals(term))
+                    .SelectMany(x => x.Value);
+
+                sources.AddRange(source);
+            }
+
+            return sources.Distinct();
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -150,9 +150,9 @@ This repository contains algorithms and data structures implemented in C# for ed
     * [Directed Weighted Graph Via Adjacency Matrix](./DataStructures/Graph/DirectedWeightedGraph.cs)
   * [Disjoint Set](./DataStructures/DisjointSet)
   * [SortedList](./DataStructures/SortedList.cs)
+  * [Inverted index](./DataStructures/InvertedIndex.cs)
   * [Unrolled linked list](./DataStructures/UnrolledList/UnrolledLinkedList.cs)
 
-
 ## Contributing
 
 You can contribute with pleasure to this repository.
