Repository: TheAlgorithms/Java
Pull request #4984 (2023-12-19 14:26:00)

Implementation of cross-correlation, CrossCorrelation test class, auto-correlation and AutoCorrelation test class
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

siriak: Please fix the PR check
![image](https://github.com/TheAlgorithms/Java/assets/29201949/e10c8df2-3b76-4727-99cf-41f6d1a8bb5f)

AthinaSw: In the details of the "Clang format linter / build" , it says this : 
--- ./src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java	(original)
+++ ./src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java	(reformatted)
@@ -34,4 +34,4 @@
         }
         return result;
     }
-}+}
I don't really understand what I sould do here
AthinaSw: > In the details of the "Clang format linter / build" , it says this : --- ./src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java (original) +++ ./src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java (reformatted) @@ -34,4 +34,4 @@ } return result; } -}+} I don't really understand what I sould do here


Ok I fixed it
AthinaSw: > Please fix the PR check ![image](https://private-user-images.githubusercontent.com/29201949/292881938-e10c8df2-3b76-4727-99cf-41f6d1a8bb5f.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MDQyOTkyMjAsIm5iZiI6MTcwNDI5ODkyMCwicGF0aCI6Ii8yOTIwMTk0OS8yOTI4ODE5MzgtZTEwYzhkZjItM2I3Ni00NzI3LTk5Y2YtNDFmNmQxYThiYjVmLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDAxMDMlMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwMTAzVDE2MjIwMFomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTk3NzcxNWJkZDgzZTZlMjcxYTU2ZWRhMmRiYmY5ZDNmMDU0NWU0Y2EwZmFhM2M4NDU0MmIxMTc5ZWVjZDgwN2MmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.q2PKdwIarQXjWNJdSbwgW9G3ZVuKQMHypHqCB_BMac0)

Done!

Patch:
diff --git a/src/main/java/com/thealgorithms/maths/AutoCorrelation.java b/src/main/java/com/thealgorithms/maths/AutoCorrelation.java
new file mode 100644
index 00000000..5b38235b
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/AutoCorrelation.java
@@ -0,0 +1,55 @@
+package com.thealgorithms.maths;
+
+/**
+ * Class for linear auto-correlation of a discrete signal
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+
+public class AutoCorrelation {
+
+    /**
+     * Discrete linear auto-correlation function.
+     * Input and output signals have starting index 0.
+     *
+     * @param x The discrete signal
+     * @return The result of the auto-correlation of signals x. The result is also a signal.
+     */
+    public static double[] autoCorrelation(double[] x) {
+
+        /*
+        To find the auto-correlation of a discrete signal x, we perform cross-correlation between x signal and itself.
+        Here's an example:
+        x=[1,2,1,1]
+        y=[1,2,1,1]
+
+        i=0:      [1,2,1,1]
+            [1,2,1,1]               result[0]=1*1=1
+
+        i=1:       [1,2,1,1]
+               [1,2,1,1]            result[1]=1*1+2*1=3
+
+        i=2:       [1,2,1,1]
+                 [1,2,1,1]          result[2]=1*2+2*1+1*1=5
+
+        i=3:       [1,2,1,1]
+                   [1,2,1,1]        result[3]=1*1+2*2+1*1+1*1=7
+
+        i=4:       [1,2,1,1]
+                     [1,2,1,1]      result[4]=2*1+1*2+1*1=5
+
+        i=5:       [1,2,1,1]
+                       [1,2,1,1]    result[5]=1*1+1*2=3
+
+        i=1:       [1,2,1,1]
+                         [1,2,1,1]  result[6]=1*1=1
+
+        result=[1,3,5,7,5,3,1]
+
+
+         */
+
+        return CrossCorrelation.crossCorrelation(x, x);
+    }
+}
diff --git a/src/main/java/com/thealgorithms/maths/CrossCorrelation.java b/src/main/java/com/thealgorithms/maths/CrossCorrelation.java
new file mode 100644
index 00000000..080e4ab7
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/CrossCorrelation.java
@@ -0,0 +1,87 @@
+package com.thealgorithms.maths;
+
+/**
+ * Class for linear cross-correlation of two discrete signals
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 1.0
+ */
+
+public class CrossCorrelation {
+
+    /**
+     * Discrete linear cross-correlation function.
+     * Input and output signals have starting index 0.
+     *
+     * @param x The first discrete signal
+     * @param y The second discrete signal
+     * @return The result of the cross-correlation of signals x,y. The result is also a signal.
+     */
+    public static double[] crossCorrelation(double[] x, double[] y) {
+        // The result signal's length is the sum of the input signals' lengths minus 1
+        double[] result = new double[x.length + y.length - 1];
+        int N = result.length;
+
+        /*
+        To find the cross-correlation between 2 discrete signals x & y, we start by "placing" the second signal
+        y under the first signal x, shifted to the left so that the last value of y meets the first value of x
+        and for every new position (i++) of the result signal, we shift y signal one position to the right, until
+        the first y-value meets the last x-value. The result-value for each position is the sum of all x*y meeting
+        values.
+        Here's an example:
+        x=[1,2,1,1]
+        y=[1,1,2,1]
+
+        i=0:      [1,2,1,1]
+            [1,1,2,1]               result[0]=1*1=1
+
+        i=1:       [1,2,1,1]
+               [1,1,2,1]            result[1]=1*2+2*1=4
+
+        i=2:       [1,2,1,1]
+                 [1,1,2,1]          result[2]=1*1+2*2+1*1=6
+
+        i=3:       [1,2,1,1]
+                   [1,1,2,1]        result[3]=1*1+2*1+1*2+1*1=6
+
+        i=4:       [1,2,1,1]
+                     [1,1,2,1]      result[4]=2*1+1*1+1*2=5
+
+        i=5:       [1,2,1,1]
+                       [1,1,2,1]    result[5]=1*1+1*1=2
+
+        i=1:       [1,2,1,1]
+                         [1,1,2,1]  result[6]=1*1=1
+
+        result=[1,4,6,6,5,2,1]
+
+
+
+
+        To find the result[i] value for each i:0->N-1, the positions of x-signal in which the 2 signals meet
+        are calculated: kMin<=k<=kMax.
+        The variable 'yStart' indicates the starting index of y in each sum calculation.
+        The variable 'count' increases the index of y-signal by 1, to move to the next value.
+         */
+        int yStart = y.length;
+        for (int i = 0; i < N; i++) {
+            result[i] = 0;
+
+            int kMin = Math.max(i - (y.length - 1), 0);
+            int kMax = Math.min(i, x.length - 1);
+
+            if (i < y.length) {
+                yStart--;
+            }
+
+            int count = 0;
+            for (int k = kMin; k <= kMax; k++) {
+                result[i] += x[k] * y[yStart + count];
+                count++;
+            }
+        }
+
+        // The calculated cross-correlation of x & y signals is returned here.
+        return result;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java b/src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java
new file mode 100644
index 00000000..cacfe590
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/AutoCorrelationTest.java
@@ -0,0 +1,37 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test class for AutoCorrelation class
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+
+public class AutoCorrelationTest {
+
+    @ParameterizedTest
+    @CsvSource({"1;2;1;1, 1;3;5;7;5;3;1", "1;2;3, 3;8;14;8;3", "1.5;2.3;3.1;4.2, 6.3;14.31;23.6;34.79;23.6;14.31;6.3"})
+
+    public void testAutoCorrelationParameterized(String input, String expected) {
+        double[] array = convertStringToArray(input);
+        double[] expectedResult = convertStringToArray(expected);
+
+        double[] result = AutoCorrelation.autoCorrelation(array);
+
+        assertArrayEquals(expectedResult, result, 0.0001);
+    }
+
+    private double[] convertStringToArray(String input) {
+        String[] elements = input.split(";");
+        double[] result = new double[elements.length];
+        for (int i = 0; i < elements.length; i++) {
+            result[i] = Double.parseDouble(elements[i]);
+        }
+        return result;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/maths/CrossCorrelationTest.java b/src/test/java/com/thealgorithms/maths/CrossCorrelationTest.java
new file mode 100644
index 00000000..a7e4f14f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/CrossCorrelationTest.java
@@ -0,0 +1,37 @@
+package com.thealgorithms.maths;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+
+/**
+ * Test class for CrossCorrelation class
+ *
+ * @author Athina-Frederiki Swinkels
+ * @version 2.0
+ */
+public class CrossCorrelationTest {
+
+    @ParameterizedTest
+    @CsvSource({"1;2;1;1, 1;1;2;1, 1;4;6;6;5;2;1", "1;2;3, 1;2;3;4;5, 5;14;26;20;14;8;3", "1;2;3;4;5, 1;2;3, 3;8;14;20;26;14;5", "1.5;2.3;3.1;4.2, 1.1;2.2;3.3, 4.95;10.89;16.94;23.21;12.65;4.62"})
+
+    public void testCrossCorrelationParameterized(String input1, String input2, String expected) {
+        double[] array1 = convertStringToArray(input1);
+        double[] array2 = convertStringToArray(input2);
+        double[] expectedResult = convertStringToArray(expected);
+
+        double[] result = CrossCorrelation.crossCorrelation(array1, array2);
+
+        assertArrayEquals(expectedResult, result, 0.0001);
+    }
+
+    private double[] convertStringToArray(String input) {
+        String[] elements = input.split(";");
+        double[] result = new double[elements.length];
+        for (int i = 0; i < elements.length; i++) {
+            result[i] = Double.parseDouble(elements[i]);
+        }
+        return result;
+    }
+}