| | | 1 | | // Licensed to the .NET Foundation under one or more agreements. |
| | | 2 | | // The .NET Foundation licenses this file to you under the MIT license. |
| | | 3 | | |
| | | 4 | | using System.Diagnostics; |
| | | 5 | | |
| | | 6 | | namespace System.Buffers |
| | | 7 | | { |
| | | 8 | | internal static class CharacterFrequencyHelper |
| | | 9 | | { |
| | | 10 | | // Same as RegexPrefixAnalyzer.Frequency. |
| | | 11 | | // https://github.com/dotnet/runtime/blob/a355d5f7db162714ee19533ca55074aa2cbd8a8c/src/libraries/System.Text.Reg |
| | | 12 | | public static ReadOnlySpan<float> AsciiFrequency => |
| | 0 | 13 | | [ |
| | 0 | 14 | | 0.000f /* '\x00' */, 0.000f /* '\x01' */, 0.000f /* '\x02' */, 0.000f /* '\x03' */, 0.000f /* '\x04' */, 0.0 |
| | 0 | 15 | | 0.000f /* '\x08' */, 0.001f /* '\x09' */, 0.000f /* '\x0A' */, 0.000f /* '\x0B' */, 0.000f /* '\x0C' */, 0.0 |
| | 0 | 16 | | 0.000f /* '\x10' */, 0.000f /* '\x11' */, 0.000f /* '\x12' */, 0.000f /* '\x13' */, 0.003f /* '\x14' */, 0.0 |
| | 0 | 17 | | 0.000f /* '\x18' */, 0.004f /* '\x19' */, 0.000f /* '\x1A' */, 0.000f /* '\x1B' */, 0.006f /* '\x1C' */, 0.0 |
| | 0 | 18 | | 8.952f /* ' ' */, 0.065f /* ' !' */, 0.420f /* ' "' */, 0.010f /* ' #' */, 0.011f /* ' $' */, 0.0 |
| | 0 | 19 | | 3.911f /* ' (' */, 3.910f /* ' )' */, 0.356f /* ' *' */, 2.775f /* ' +' */, 1.411f /* ' ,' */, 0.1 |
| | 0 | 20 | | 1.199f /* ' 0' */, 0.870f /* ' 1' */, 0.729f /* ' 2' */, 0.491f /* ' 3' */, 0.335f /* ' 4' */, 0.2 |
| | 0 | 21 | | 0.234f /* ' 8' */, 0.196f /* ' 9' */, 0.144f /* ' :' */, 0.983f /* ' ;' */, 0.357f /* ' <' */, 0.6 |
| | 0 | 22 | | 0.007f /* ' @' */, 0.763f /* ' A' */, 0.229f /* ' B' */, 0.551f /* ' C' */, 0.306f /* ' D' */, 0.4 |
| | 0 | 23 | | 0.131f /* ' H' */, 0.489f /* ' I' */, 0.031f /* ' J' */, 0.035f /* ' K' */, 0.301f /* ' L' */, 0.2 |
| | 0 | 24 | | 0.288f /* ' P' */, 0.034f /* ' Q' */, 0.380f /* ' R' */, 0.730f /* ' S' */, 0.675f /* ' T' */, 0.2 |
| | 0 | 25 | | 0.084f /* ' X' */, 0.023f /* ' Y' */, 0.023f /* ' Z' */, 0.591f /* ' [' */, 0.085f /* ' \' */, 0.5 |
| | 0 | 26 | | 0.001f /* ' `' */, 4.596f /* ' a' */, 1.296f /* ' b' */, 2.081f /* ' c' */, 2.005f /* ' d' */, 6.9 |
| | 0 | 27 | | 1.024f /* ' h' */, 3.750f /* ' i' */, 0.286f /* ' j' */, 0.439f /* ' k' */, 2.913f /* ' l' */, 1.4 |
| | 0 | 28 | | 1.444f /* ' p' */, 0.231f /* ' q' */, 4.220f /* ' r' */, 3.924f /* ' s' */, 5.312f /* ' t' */, 2.1 |
| | 0 | 29 | | 0.992f /* ' x' */, 1.067f /* ' y' */, 0.181f /* ' z' */, 0.391f /* ' {' */, 0.056f /* ' |' */, 0.3 |
| | 0 | 30 | | ]; |
| | | 31 | | |
| | | 32 | | public static void GetSingleStringMultiCharacterOffsets(string value, bool ignoreCase, out int ch2Offset, out in |
| | | 33 | | { |
| | 0 | 34 | | Debug.Assert(value.Length > 1); |
| | 0 | 35 | | Debug.Assert(!ignoreCase || char.IsAscii(value[0])); |
| | | 36 | | |
| | 0 | 37 | | ch2Offset = IndexOfAsciiCharWithLowestFrequency(value, ignoreCase); |
| | 0 | 38 | | ch3Offset = 0; |
| | | 39 | | |
| | 0 | 40 | | if (ch2Offset < 0) |
| | | 41 | | { |
| | | 42 | | // We have fewer than 2 ASCII chars in the value. |
| | 0 | 43 | | Debug.Assert(!ignoreCase); |
| | | 44 | | |
| | | 45 | | // We don't have a frequency table for non-ASCII characters, pick a random one. |
| | 0 | 46 | | ch2Offset = value.Length - 1; |
| | | 47 | | } |
| | | 48 | | |
| | 0 | 49 | | if (value.Length > 2) |
| | | 50 | | { |
| | 0 | 51 | | ch3Offset = IndexOfAsciiCharWithLowestFrequency(value, ignoreCase, excludeIndex: ch2Offset); |
| | | 52 | | |
| | 0 | 53 | | if (ch3Offset < 0) |
| | | 54 | | { |
| | | 55 | | // We have fewer than 3 ASCII chars in the value. |
| | 0 | 56 | | if (ignoreCase) |
| | | 57 | | { |
| | | 58 | | // We can still use N=2. |
| | 0 | 59 | | ch3Offset = 0; |
| | | 60 | | } |
| | | 61 | | else |
| | | 62 | | { |
| | | 63 | | // We don't have a frequency table for non-ASCII characters, pick a random one. |
| | 0 | 64 | | ch3Offset = value.Length - 1; |
| | | 65 | | |
| | 0 | 66 | | if (ch2Offset == ch3Offset) |
| | | 67 | | { |
| | 0 | 68 | | ch2Offset--; |
| | | 69 | | } |
| | | 70 | | } |
| | | 71 | | } |
| | | 72 | | } |
| | | 73 | | |
| | 0 | 74 | | Debug.Assert(ch2Offset != 0); |
| | 0 | 75 | | Debug.Assert(ch2Offset != ch3Offset); |
| | | 76 | | |
| | 0 | 77 | | if (ch3Offset > 0 && ch3Offset < ch2Offset) |
| | | 78 | | { |
| | 0 | 79 | | (ch2Offset, ch3Offset) = (ch3Offset, ch2Offset); |
| | | 80 | | } |
| | 0 | 81 | | } |
| | | 82 | | |
| | | 83 | | private static int IndexOfAsciiCharWithLowestFrequency(ReadOnlySpan<char> span, bool ignoreCase, int excludeInde |
| | | 84 | | { |
| | 0 | 85 | | float minFrequency = float.MaxValue; |
| | 0 | 86 | | int minIndex = -1; |
| | | 87 | | |
| | | 88 | | // Exclude i = 0 as we've already decided to use the first character. |
| | 0 | 89 | | for (int i = 1; i < span.Length; i++) |
| | | 90 | | { |
| | 0 | 91 | | if (i == excludeIndex) |
| | | 92 | | { |
| | | 93 | | continue; |
| | | 94 | | } |
| | | 95 | | |
| | 0 | 96 | | char c = span[i]; |
| | | 97 | | |
| | | 98 | | // We don't have a frequency table for non-ASCII characters, so they are ignored. |
| | 0 | 99 | | if (char.IsAscii(c)) |
| | | 100 | | { |
| | 0 | 101 | | float frequency = AsciiFrequency[c]; |
| | | 102 | | |
| | 0 | 103 | | if (ignoreCase) |
| | | 104 | | { |
| | | 105 | | // Include the alternative character that will also match. |
| | 0 | 106 | | frequency += AsciiFrequency[c ^ 0x20]; |
| | | 107 | | } |
| | | 108 | | |
| | | 109 | | // Avoiding characters from the front of the value for the 2nd and 3rd character |
| | | 110 | | // results in 18 % fewer false positive 3-char matches on "The Adventures of Sherlock Holmes". |
| | 0 | 111 | | if (i <= 2) |
| | | 112 | | { |
| | 0 | 113 | | frequency *= 1.5f; |
| | | 114 | | } |
| | | 115 | | |
| | 0 | 116 | | if (frequency <= minFrequency) |
| | | 117 | | { |
| | 0 | 118 | | minFrequency = frequency; |
| | 0 | 119 | | minIndex = i; |
| | | 120 | | } |
| | | 121 | | } |
| | | 122 | | } |
| | | 123 | | |
| | 0 | 124 | | return minIndex; |
| | | 125 | | } |
| | | 126 | | } |
| | | 127 | | } |
| | | 128 | | |