source: trunk/CrypPlugins/WordPatterns/WordPatterns.cs

Last change on this file was 8983, checked in by kopal, 10 months ago

Complete CrypTool 2 project

  • renamed "Cryptool" namespace to "CrypTool" namespace
File size: 13.3 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using CrypTool.PluginBase;
5using CrypTool.PluginBase.Miscellaneous;
6using System.ComponentModel;
7
8namespace WordPatterns
9{
10    /*
11     * Proposed changes and enhancements:
12     * - multiple word search with one TextInput (split words at whitespace)
13     * - enter max match number
14     * - enter pattern in number format (like 1-2-2-1)
15     * - add filter function (see Borland C++ tool)
16     * - save last input words and propose them to user
17     * - improve performance
18     * - support wildcard (*)
19     */
20    [Author("Matthäus Wander", "wander@CrypTool.org", "Fachgebiet Verteilte Systeme, Universität Duisburg-Essen", "http://www.vs.uni-due.de")]
21    [PluginInfo("WordPatterns.Properties.Resources", "PluginCaption", "PluginTooltip", "WordPatterns/DetailedDescription/doc.xml", "WordPatterns/Images/icon.png")]
22    [ComponentCategory(ComponentCategory.CryptanalysisGeneric)]
23    public class WordPatterns : ICrypComponent
24    {
25        #region Private stuff
26
27        private WordPatternsSettings settings = new WordPatternsSettings();
28
29        private string inputText;
30        private string[] inputDict;
31        private string outputText;
32
33        private List<string> results = new List<string>();
34        List<List<Pattern>> inputPatterns;
35        Dictionary<int, Dictionary<Pattern, IList<string>>> PatternsOfSize = null;
36        private string[] inputWords;
37        private int[] sizes, sorted, sortedInverse;
38
39        private bool stop = false;
40
41        #endregion
42
43        #region Properties
44
45        [PropertyInfo(Direction.InputData, "InputTextCaption", "InputTextTooltip", true)]
46        public string InputText
47        {
48            get
49            {
50                return inputText;
51            }
52            set
53            {
54                inputText = value;
55                OnPropertyChanged("InputText");
56            }
57        }
58
59        [PropertyInfo(Direction.InputData, "InputDictCaption", "InputDictTooltip", true)]
60        public string[] InputDict
61        {
62            get
63            {
64                return inputDict;
65            }
66            set
67            {
68                inputDict = value;
69                PatternsOfSize = null;
70                OnPropertyChanged("InputDict");
71            }
72        }
73
74        [PropertyInfo(Direction.OutputData, "OutputTextCaption", "OutputTextTooltip", false)]
75        public string OutputText
76        {
77            get { return outputText; }
78            private set
79            {
80                outputText = value;
81                OnPropertyChanged("OutputText");
82            }
83        }
84
85        public bool CaseSensitive
86        {
87            get
88            {
89                return settings.CaseSelection == Case.Sensitive;
90            }
91        }
92
93        #endregion
94
95        #region IPlugin Members
96
97        public event StatusChangedEventHandler OnPluginStatusChanged;
98
99        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
100        private void GuiLogMessage(string p, NotificationLevel notificationLevel)
101        {
102            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
103        }
104
105        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
106        private void ProgressChanged(double value, double max)
107        {
108            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
109        }
110
111        public ISettings Settings
112        {
113            get { return settings; }
114            set { settings = (WordPatternsSettings)value; }
115        }
116
117        public System.Windows.Controls.UserControl Presentation
118        {
119            get { return null; }
120        }
121
122        public void PreExecution()
123        {
124            stop = false;
125        }
126
127        public void Execute()
128        {
129            if (inputText == null)
130            {
131                OutputText = "";
132                return;
133            }
134
135            if (inputDict == null)
136                return;
137
138            // If not already done, calculate pattern for each dictionary word
139
140            if (PatternsOfSize == null)
141            {
142                PatternsOfSize = new Dictionary<int, Dictionary<Pattern, IList<string>>>();
143
144                foreach (string word in inputDict)
145                {
146                    if (stop) break;
147
148                    Pattern p = new Pattern(word, CaseSensitive);
149
150                    if (!PatternsOfSize.ContainsKey(word.Length))
151                        PatternsOfSize[word.Length] = new Dictionary<Pattern, IList<string>>();
152
153                    if (!PatternsOfSize[word.Length].ContainsKey(p))
154                        PatternsOfSize[word.Length][p] = new List<string>();
155
156                    PatternsOfSize[word.Length][p].Add(word);
157                }
158            }
159
160            // remove separator characters from inputText
161
162            foreach (char c in settings.Separators)
163                inputText = inputText.Replace(c.ToString(), "");
164
165            // get input words and their patterns
166
167            inputWords = inputText.Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
168            inputPatterns = inputWords.Select(w => new List<Pattern>()).ToList();
169
170            for (int i = 0; i < inputWords.Length; i++)
171                if (PatternsOfSize.ContainsKey(inputWords[i].Length))
172                    foreach (var p in PatternsOfSize[inputWords[i].Length])
173                        if (new CharacterMap().add(p.Value[0], inputWords[i], settings.Homophonic))
174                            inputPatterns[i].Add(p.Key);
175
176            // sort patterns according to the number of possible words in order to minimize the recursion calls
177
178            sizes = Enumerable.Range(0, inputWords.Length).Select(i => inputPatterns[i].Select(p => PatternsOfSize[inputWords[i].Length][p].Count).Sum()).ToArray();
179            if (sizes.Length == 0 || sizes[0] == 0)
180            {
181                OutputText = "";
182                return;
183            }
184
185            sorted = Enumerable.Range(0, inputWords.Length).ToArray();
186            if (settings.Sort)
187                Array.Sort(sorted, (i, j) => sizes[i].CompareTo(sizes[j]));
188            sortedInverse = new int[sorted.Length];
189            for (int i = 0; i < sorted.Length; i++)
190                sortedInverse[sorted[i]] = i;
191
192            results.Clear();
193            recmatch(new List<string>(), new CharacterMap());
194            results.Sort();
195
196            OutputText = String.Join("\r\n", results);
197        }
198
199        void recmatch(List<string> w, CharacterMap cm)
200        {
201            if (stop) return;
202
203            int depth = w.Count;
204
205            if (depth == inputPatterns.Count)
206            {
207                results.Add(String.Join(" ", sortedInverse.Select(j => w[j])));
208                return;
209            }
210
211            int index = sorted[depth];
212            string cipher = inputWords[index];
213
214            int i = 0;
215
216            foreach (var pp in inputPatterns[index])
217            {
218                foreach (string plain in PatternsOfSize[cipher.Length][pp])
219                {
220                    if (depth == 0)
221                        ProgressChanged(++i, sizes[index]);
222
223                    CharacterMap new_cm = new CharacterMap(cm);
224                    if (new_cm.add(plain, cipher, settings.Homophonic))
225                    {
226                        w.Add(plain);
227                        recmatch(w, new_cm);
228                        w.RemoveAt(depth);
229                    }
230                }
231            }
232        }
233
234        internal class CharacterMap
235        {
236            public Dictionary<char, HashSet<char>> plain2cipher = new Dictionary<char, HashSet<char>>();
237            public Dictionary<char, char> cipher2plain = new Dictionary<char, char>();
238
239            public CharacterMap()
240            {
241            }
242
243            public CharacterMap(CharacterMap cm)
244            {
245                cipher2plain = new Dictionary<char, char>(cm.cipher2plain);
246                plain2cipher = new Dictionary<char, HashSet<char>>();
247                foreach (KeyValuePair<char, HashSet<char>> x in cm.plain2cipher)
248                    plain2cipher[x.Key] = new HashSet<char>(x.Value);
249            }
250
251            public bool add(string plain, string cipher, bool homophonic)
252            {
253                for (int i = 0; i < plain.Length; i++)
254                    if (!add(plain[i], cipher[i], homophonic)) return false;
255
256                return true;
257            }
258
259            public bool add(char plain, char cipher, bool homophonic)
260            {
261                if (cipher2plain.ContainsKey(cipher))
262                    return cipher2plain[cipher] == plain;
263
264                if (!plain2cipher.ContainsKey(plain))
265                    plain2cipher.Add(plain, new HashSet<char>());
266                else if (!homophonic)
267                    return plain2cipher[plain].Contains(cipher);
268
269                plain2cipher[plain].Add(cipher);
270                cipher2plain.Add(cipher, plain);
271
272                return true;
273            }
274        }
275
276        internal struct Pattern
277        {
278            private const int PRIME = 16777619;
279
280            private readonly int[] patternArray;
281            private readonly int hashCode;
282            public Dictionary<char, int> seenLetters;
283            public static string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
284
285            internal Pattern(string word, bool caseSensitive)
286            {
287                if (!caseSensitive)
288                    word = word.ToLower();
289
290                patternArray = new int[word.Length];
291                hashCode = -2128831035; // int32 counterpart of uint32 2166136261
292
293                seenLetters = new Dictionary<char, int>(15);
294                int letterNumber = 0;
295
296                for (int i = 0; i < word.Length; i++)
297                {
298                    if (seenLetters.ContainsKey(word[i])) // letter already seen?
299                    {
300                        patternArray[i] = seenLetters[word[i]]; // get letter number
301                    }
302                    else
303                    {
304                        seenLetters[word[i]] = patternArray[i] = ++letterNumber; // create new letter number
305                    }
306
307                    // FNV-1 hashing
308                    hashCode = (hashCode * PRIME) ^ patternArray[i];
309                }
310
311                seenLetters = null;
312            }
313
314            public string proxy()
315            {
316                return new String(patternArray.Select(i => alphabet[i - 1]).ToArray());
317            }
318
319            /// <summary>
320            /// Returns pre-calculated hash code.
321            /// </summary>
322            /// <returns></returns>
323            public override int GetHashCode()
324            {
325                return hashCode;
326            }
327
328            /// <summary>
329            /// In-depth comparison of pattern array contents.
330            /// </summary>
331            /// <param name="obj"></param>
332            /// <returns></returns>
333            public override bool Equals(object right)
334            {
335                if (right == null)
336                    return false;
337
338                // Never true for value types
339                //if (object.ReferenceEquals(this, right))
340                //    return true;
341
342                // Using the as/is operators can break symmetry requirement for reference types.
343                // However this does not apply for value types.
344                //if (this.GetType() != right.GetType())
345                //    return false;
346                if (!(right is Pattern))
347                    return false;
348
349                return this == (Pattern)right;
350            }
351
352            public static bool operator ==(Pattern left, Pattern right)
353            {
354                if (left.hashCode != right.hashCode)
355                    return false;
356
357                if (left.patternArray.Length != right.patternArray.Length)
358                    return false;
359
360                for (int i = 0; i < left.patternArray.Length; i++)
361                {
362                    // uneven pattern content
363                    if (left.patternArray[i] != right.patternArray[i])
364                        return false;
365                }
366
367                return true;
368            }
369
370            public static bool operator !=(Pattern left, Pattern right)
371            {
372                return !(left == right);
373            }
374        }
375
376        public void PostExecution()
377        {
378            GuiLogMessage("PostExecution has been called. Cleaning pattern dictionary...", NotificationLevel.Info);
379            PatternsOfSize = null;
380        }
381
382        public void Stop()
383        {
384            stop = true;
385        }
386
387        public void Initialize()
388        {
389        }
390
391        public void Dispose()
392        {
393        }
394
395        #endregion
396
397        #region INotifyPropertyChanged Members
398
399        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
400        private void OnPropertyChanged(string p)
401        {
402            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(p));
403        }
404
405        #endregion
406
407    }
408}
Note: See TracBrowser for help on using the repository browser.