source: trunk/CrypPlugins/CostFunction/CostFunction.cs @ 1375

Last change on this file since 1375 was 1375, checked in by malischewski, 12 years ago

Started implementation of new costfunction for genetic algorithm analysis of transposition cipher.
note: is listed as "weighted bigrams/trigrams" in the plugin, but not functional yet (will be tomorrow, probably)

File size: 24.8 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Collections;
20using System.Linq;
21using System.Text;
22using Cryptool.PluginBase.Cryptography;
23using Cryptool.PluginBase;
24using Cryptool.PluginBase.Miscellaneous;
25using Cryptool.PluginBase.Analysis;
26using System.ComponentModel;
27using Cryptool.PluginBase.Control;
28using System.IO;
29using System.Text.RegularExpressions;
30using System.Threading;
31namespace Cryptool.Plugins.CostFunction
32{
33    [Author("Nils Kopal", "Nils.Kopal@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
34    [PluginInfo(false, "CostFunction", "CostFunction", null, "CostFunction/icon.png")]
35    public class CostFunction : IAnalysisMisc
36    {
37        #region private variables
38        private CostFunctionSettings settings = new CostFunctionSettings();
39        private byte[] inputText = null;
40        private byte[] outputText = null;
41        private double value = 0;
42        private Boolean stopped = true;
43        private IControlCost controlSlave;
44        private String bigramInput;
45        private double[,] bigramMatrix;
46        private IDictionary<string, double[]> corpusGrams;
47
48        private IDictionary<string, double[]> corpusBigrams; // Used for Weighted Bigrams/Trigrams Cost function
49        private IDictionary<string, double[]> corpusTrigrams;
50
51        private DataManager dataMgr = new DataManager();
52        private const string DATATYPE = "transposition";
53
54        private IDictionary<String, DataFileMetaInfo> txtList;
55        private IDictionary<int, IDictionary<string, double[]>> statistics;
56
57        #endregion
58        #region internal constants
59        internal const int ABSOLUTE = 0;
60        internal const int PERCENTAGED = 1;
61        internal const int LOG2 = 2;
62        internal const int SINKOV = 3;
63        #endregion
64        #region CostFunctionInOut
65
66        [PropertyInfo(Direction.InputData, "Text Input", "Input your Text here", "", DisplayLevel.Beginner)]
67        public byte[] InputText
68        {
69            get
70            {
71                return inputText;
72            }
73            set
74            {
75                this.inputText = value;
76                OnPropertyChanged("InputText");
77            }
78        }
79
80        [PropertyInfo(Direction.OutputData, "Text Output", "Your Text will be send here", "", DisplayLevel.Beginner)]
81        public byte[] OutputText
82        {
83            get
84            {
85                return outputText;
86            }
87            set
88            {
89                this.outputText = value;
90                OnPropertyChanged("OutputText");
91            }
92        }
93
94        [PropertyInfo(Direction.OutputData, "Value", "The value of the function will be send here", "", DisplayLevel.Beginner)]
95        public double Value
96        {
97            get
98            {
99                return value;
100            }
101            set
102            {
103                this.value = value;
104                OnPropertyChanged("Value");
105            }
106        }
107
108        [PropertyInfo(Direction.ControlSlave, "SDES Slave", "Direct access to SDES.", "", DisplayLevel.Beginner)]
109        public IControlCost ControlSlave
110        {
111            get
112            {
113                if (controlSlave == null)
114                    controlSlave = new CostFunctionControl(this);
115                return controlSlave;
116            }
117        }
118
119        #endregion
120
121        #region IPlugin Members
122
123        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
124        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
125
126
127        public ISettings Settings
128        {
129            get { return this.settings; }
130            set { this.settings = (CostFunctionSettings)value; }
131        }
132
133        public System.Windows.Controls.UserControl Presentation
134        {
135            get { return null; }
136        }
137
138        public System.Windows.Controls.UserControl QuickWatchPresentation
139        {
140            get { return null; }
141        }
142
143        public void PreExecution()
144        {
145            this.stopped = false;
146        }
147
148        public void Execute()
149        {
150            if (this.InputText is Object && this.stopped == false)
151            {
152                int bytesToUse = 0;
153                try
154                {
155                    bytesToUse = int.Parse(settings.BytesToUse);
156                }
157                catch (Exception ex)
158                {
159                    GuiLogMessage("Entered bytesToUse is not an integer: " + ex.Message, NotificationLevel.Error);
160                    return;
161                }
162
163                if (bytesToUse > this.InputText.Length)
164                {
165                    bytesToUse = 0;
166                }
167
168                byte[] array;
169
170                if (bytesToUse > 0)
171                {
172                    //Create a new Array of size of bytesToUse if needed
173                    array = new byte[bytesToUse];
174                    for (int i = 0; i < bytesToUse && i < this.InputText.Length; i++)
175                    {
176                        array[i] = InputText[i];
177                    }
178                }
179                else
180                {
181                    array = this.InputText;
182                }
183
184                ProgressChanged(0.5, 1);
185                bigramInput = ByteArrayToString(array);
186                switch (settings.FunctionType)
187                {
188
189                    case 0: // Index of Coincedence
190                        this.Value = calculateIndexOfCoincidence(array);
191                        break;
192
193                    case 1: // Entropy
194                        this.Value = calculateEntropy(array);
195                        break;
196
197                    case 2: // Log 2 Bigrams
198                        this.Value = calculateNGrams(bigramInput, 2, 2);
199                        break;
200
201                    case 3: // sinkov Bigrams
202                        this.Value = calculateNGrams(bigramInput, 2, 3);
203                        break;
204                    case 4: //percentaged Bigrams
205                        this.Value = calculateNGrams(bigramInput, 2, 1);
206                        break;
207                    case 5: //regular expressions
208                        this.Value = regex(bigramInput);
209                        break;
210                    case 6: // Weighted Bigrams/Trigrams (used by genetic algorithm in transposition analyser
211                        this.Value = calculateWeighted(bigramInput);
212                        break;
213
214                    default:
215                        this.Value = -1;
216                        break;
217                }//end switch               
218
219                this.OutputText = this.InputText;
220                ProgressChanged(1, 1);
221
222            }//end if
223
224        }
225
226
227
228        public void PostExecution()
229        {
230            this.stopped = true;
231        }
232
233        public void Pause()
234        {
235
236        }
237
238        public void Stop()
239        {
240            this.stopped = false;
241        }
242
243        public void Initialize()
244        {
245
246        }
247
248        public void Dispose()
249        {
250
251        }
252
253        #endregion
254
255        #region INotifyPropertyChanged Members
256
257        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
258
259        public void OnPropertyChanged(string name)
260        {
261            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
262        }
263
264        private void ProgressChanged(double value, double max)
265        {
266            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
267        }
268
269        public void GuiLogMessage(string p, NotificationLevel notificationLevel)
270        {
271            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
272        }
273
274        #endregion
275
276        #region IPlugin Members
277
278        public event StatusChangedEventHandler OnPluginStatusChanged;
279
280        #endregion
281
282        #region private methods
283
284
285        //public double contains(string input)
286        //{
287        //    if (settings.Contains == null)
288        //    {
289        //        GuiLogMessage("There is no text to be searched for. Please insert text in the 'Contains text / Regular Expression' - Textarea", NotificationLevel.Error);
290        //        return new Double();
291        //    }
292
293        //    if (input.Contains(settings.Contains))
294        //    {
295        //        return 1.0;
296        //    }
297        //    return -1.0;
298        //}
299        public double calculateWeighted(string input)
300        {
301
302
303            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
304           
305            if (corpusBigrams == null)
306            {
307                if (corpusTrigrams == null)
308                {
309
310                    corpusBigrams = GetStatistics(2); // Get Known Language statistics for Bigrams
311                    corpusTrigrams = GetStatistics(3); // and Trigrams
312                }
313
314            }
315            input = input.ToUpper();
316
317            /* debug foreach (KeyValuePair<string,double[]> g in corpusTrigrams)
318             {
319                 GuiLogMessage(corpusTrigrams[g.Key][0].ToString()+ " "+g.Key, NotificationLevel.Debug);
320             } */
321
322
323            Dictionary<string, double> inputBiGrams = new Dictionary<string,double>();
324            Dictionary<string, double> inputTriGrams = new Dictionary<string,double>();
325
326            // Count input Bigrams
327            foreach (string g in GramTokenizer.tokenize(input, 2, false))
328            {
329                if (inputBiGrams.ContainsKey(g))
330                {
331                    inputBiGrams[g] = inputBiGrams[g] + 1;
332                }
333                else
334                {
335                    inputBiGrams.Add(g, 0);
336                }
337            }
338            //debug
339            foreach (KeyValuePair<string, double[]> g in corpusBigrams)
340            {
341                GuiLogMessage(corpusBigrams[g.Key][0].ToString() + " " + g.Key + " " + corpusBigrams[g.Key][1].ToString(), NotificationLevel.Debug);
342            }
343           
344            // Count input TriGrams
345            foreach (string g in GramTokenizer.tokenize(input, 3, false))
346            {
347                if (inputTriGrams.ContainsKey(g))
348                {
349                    inputTriGrams[g] = inputTriGrams[g] + 1;
350                }
351                else
352                {
353                    inputTriGrams.Add(g, 0);
354                }
355            }
356
357            // First part of the equation: Sum up all [K_b (i,j) - D_b (i,j)]
358            double bigramscore = 0.0;
359            foreach (KeyValuePair<string, double[]> g in corpusBigrams)
360            {
361                // bigramscore += g.Value[1] - inputBiGrams[g]/inputBiGrams.Sum<value;
362            }
363
364            // Second part of the equation: Sum up all [K_t (i,j) - D_t (i,j)]
365           
366
367            return bigramscore;
368        }//end Execute
369
370        public double regex(string input)
371        {
372            if (settings.RegEx == null)
373            {
374                GuiLogMessage("There is no Regular Expression to be searched for. Please insert regex in the 'Regular Expression' - Textarea", NotificationLevel.Error);
375                return new Double();
376            }
377            try
378            {
379                Match match = Regex.Match(input, settings.RegEx);
380                if (match.Success)
381                {
382                    return 1.0;
383                }
384                else
385                {
386                    return -1.0;
387                }
388            }
389            catch (Exception e)
390            {
391                GuiLogMessage(e.Message, NotificationLevel.Error);
392                return -1.0;
393            }
394
395        }
396
397
398        /// <summary>
399        /// Calculates the Index of Coincidence multiplied with 100 of
400        /// a given byte array
401        ///
402        /// for example a German text has about 7.62
403        ///           an English text has about 6.61
404        /// </summary>
405        /// <param name="text">text to use</param>
406        /// <returns>Index of Coincidence</returns>
407        public double calculateIndexOfCoincidence(byte[] text)
408        {
409            return calculateIndexOfCoincidence(text, text.Length);
410        }
411
412        /// <summary>
413        /// Calculates the Index of Coincidence multiplied with 100 of
414        /// a given byte array
415        ///
416        /// for example a German text has about 7.62
417        ///           an English text has about 6.61
418        /// </summary>
419        /// <param name="text">text to use</param>
420        /// <param name="text">bytesToUse</param>
421        /// <returns>Index of Coincidence</returns>
422        public double calculateIndexOfCoincidence(byte[] text, int bytesToUse)
423        {
424            if (bytesToUse > text.Length)
425                bytesToUse = text.Length;
426
427            double[] n = new double[256];
428            //count all ASCII symbols
429            int counter = 0;
430            foreach (byte b in text)
431            {
432                n[b]++;
433                counter++;
434                if (counter == bytesToUse)
435                    break;
436            }
437
438            double coindex = 0;
439            //sum them
440            for (int i = 0; i < n.Length; i++)
441            {
442                coindex = coindex + n[i] * (n[i] - 1);
443            }
444
445            coindex = coindex / (bytesToUse);
446            coindex = coindex / (bytesToUse - 1);
447
448            return coindex * 100;
449
450        }//end calculateIndexOfCoincidence
451
452
453        private int lastUsedSize = -1;
454        private double[] xlogx;
455        private Mutex prepareMutex = new Mutex();
456
457        private void prepareEntropy(int size)
458        {
459            xlogx = new double[size + 1];
460            //precomputations for fast entropy calculation     
461            xlogx[0] = 0.0;
462            for (int i = 1; i <= size; i++)
463                xlogx[i] = -1.0 * i * Math.Log(i / (double)size) / Math.Log(2.0);
464        }
465
466        /// <summary>
467        /// Calculates the Entropy of a given byte array
468        /// for example a German text has about 4.0629
469        /// </summary>
470        /// <param name="text">text to use</param>
471        /// <returns>Entropy</returns>
472        public double calculateEntropy(byte[] text)
473        {
474            return calculateEntropy(text, text.Length);
475        }
476
477        /// <summary>
478        /// Calculates the Entropy of a given byte array
479        /// for example a German text has about 4.0629
480        /// </summary>
481        /// <param name="text">text to use</param>
482        /// <returns>Entropy</returns>
483        public double calculateEntropy(byte[] text, int bytesToUse)
484        {
485            return NativeCryptography.Crypto.calculateEntropy(text, bytesToUse);
486            if (bytesToUse > text.Length)
487                bytesToUse = text.Length;
488
489            if (lastUsedSize != bytesToUse)
490            {
491                try
492                {
493                    prepareMutex.WaitOne();
494                    if (lastUsedSize != bytesToUse)
495                    {
496                        prepareEntropy(bytesToUse);
497                        lastUsedSize = bytesToUse;
498                    }
499                }
500                finally
501                {
502                    prepareMutex.ReleaseMutex();
503                }
504            }
505
506            int[] n = new int[256];
507            //count all ASCII symbols
508            for (int counter = 0; counter < bytesToUse; counter++)
509            {
510                n[text[counter]]++;
511            }
512
513            double entropy = 0;
514            //calculate probabilities and sum entropy
515            for (int i = 0; i < 256; i++)
516                entropy += xlogx[n[i]];
517
518            return entropy / (double)bytesToUse;
519
520        }//end calculateEntropy
521
522        /// <summary>
523        /// This method calculates a trigram log2 score of a given text on the basis of a given grams dictionary.
524        /// Case is insensitive.
525        /// </summary>
526        /// <param name="input">The text to be scored</param>
527        /// <param name="length">n-gram length</param>
528        /// <returns>The trigram score result</returns>
529        public double calculateNGrams(string input, int length, int valueSelection)
530        {
531            this.statistics = new Dictionary<int, IDictionary<string, double[]>>();
532            double score = 0;
533            if (corpusGrams == null)
534            { corpusGrams = GetStatistics(length); }
535            input = input.ToUpper();
536            // FIXME: case handling?
537
538            HashSet<string> inputGrams = new HashSet<string>();
539
540            foreach (string g in GramTokenizer.tokenize(input, length, false))
541            {
542                // ensure each n-gram is counted only once
543                if (inputGrams.Add(g))
544                {
545                    if (corpusGrams.ContainsKey(g))
546                    {
547                        score += corpusGrams[g][valueSelection];
548
549                    }
550                }
551            }
552
553            return score;
554        }
555        public IDictionary<string, double[]> GetStatistics(int gramLength)
556        {
557            // FIXME: inputTriGrams is not being used!
558
559            // FIXME: implement exception handling
560            if (!statistics.ContainsKey(gramLength))
561            {
562                //GuiLogMessage("Trying to load default statistics for " + gramLength + "-grams", NotificationLevel.Info);
563                statistics[gramLength] = LoadDefaultStatistics(gramLength);
564            }
565
566            return statistics[gramLength];
567        }
568
569        private IDictionary<string, double[]> LoadDefaultStatistics(int length)
570        {
571            txtList = dataMgr.LoadDirectory(DATATYPE);
572
573            return calculateAbsolutes(txtList["2gram.txt"].DataFile.FullName, length);
574        }
575
576        private IDictionary<string, double[]> calculateAbsolutes(String path, int length)
577        {
578
579
580            Dictionary<string, double[]> grams = new Dictionary<string, double[]>();
581            int checkLength;
582            StreamReader reader = new StreamReader(path);
583            String text = reader.ReadToEnd();
584
585            text.ToUpper();
586            text = Regex.Replace(text, "[^A-Z]*", "");
587
588            if (length == 2)
589            {
590                checkLength = text.Length - 1;
591            }
592            else
593            {
594                checkLength = text.Length - 2;
595            }
596            for (int i = 0; i < checkLength; i++)
597            {
598                char a = text[i];
599                char b = text[i + 1];
600                String key;
601                if (length == 3) // Trigrams
602                {
603                    char c = text[i + 2];
604                    key = a.ToString();
605                    key = key + b.ToString();
606                    key = key + c.ToString();
607                }
608                else // Bigrams
609                {
610                    key = a.ToString();
611                    key = key + b.ToString();
612                }
613
614                if (!grams.ContainsKey(key))
615                {
616                    grams.Add(key, new double[] { 1, 0, 0, 0}); 
617                }
618                else
619                {
620                    grams[key][0] = grams[key][0] + 1.0;
621                }
622            }
623
624            double sum = grams.Values.Sum(item => item[ABSOLUTE]);
625            GuiLogMessage("Sum of all n-gram counts is: " + sum, NotificationLevel.Debug);
626
627            // calculate scaled values
628            foreach (double[] g in grams.Values)
629            {
630                g[PERCENTAGED] = g[ABSOLUTE] / sum;
631                g[LOG2] = Math.Log(g[ABSOLUTE], 2);
632                g[SINKOV] = Math.Log(g[PERCENTAGED], Math.E);
633            }
634
635
636
637            return grams;
638        }
639
640        public string ByteArrayToString(byte[] arr)
641        {
642            System.Text.ASCIIEncoding enc = new System.Text.ASCIIEncoding();
643            return enc.GetString(arr);
644        }
645
646
647        #endregion
648
649
650    }
651
652    #region slave
653
654    public class CostFunctionControl : IControlCost
655    {
656        public event IControlStatusChangedEventHandler OnStatusChanged;
657        #region IControlCost Members
658
659        private CostFunction plugin;
660
661        #endregion
662
663        /// <summary>
664        /// Constructor
665        /// </summary>
666        /// <param name="plugin"></param>
667        public CostFunctionControl(CostFunction plugin)
668        {
669            this.plugin = plugin;
670        }
671
672        public int getBytesToUse()
673        {
674            try
675            {
676                return int.Parse(((CostFunctionSettings)this.plugin.Settings).BytesToUse);
677            }
678            catch (Exception ex)
679            {
680                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
681            }
682        }
683
684        /// <summary>
685        /// Returns the relation operator of the cost function which is set by by CostFunctionSettings
686        /// </summary>
687        /// <returns>RelationOperator</returns>
688        public RelationOperator getRelationOperator()
689        {
690            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
691            {
692                case 0: //Index of coincidence
693                    return RelationOperator.LargerThen;
694                case 1: //Entropy
695                    return RelationOperator.LessThen;
696                case 2: // Bigrams: log 2
697                    return RelationOperator.LessThen;
698                case 3: // Sinkov
699                    return RelationOperator.LargerThen;
700                case 4: // percentage
701                    return RelationOperator.LargerThen;
702                case 5: // Regular Expression
703                    return RelationOperator.LargerThen;
704                case 6: // Weighted Bigrams/Trigrams
705                    return RelationOperator.LargerThen;
706
707                default:
708                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
709            }//end switch
710        }//end getRelationOperator
711
712        /// <summary>
713        /// Calculates the cost function of the given text
714        ///
715        /// Cost function can be set by CostFunctionSettings
716        /// This algorithm uses a bytesToUse which can be set by CostFunctionSettings
717        /// If bytesToUse is set to 0 it uses the whole text
718        ///
719        /// </summary>
720        /// <param name="text"></param>
721        /// <returns>cost</returns>
722        public double calculateCost(byte[] text)
723        {
724            int bytesToUse = 0;
725            try
726            {
727                bytesToUse = ((CostFunctionSettings)this.plugin.Settings).BytesToUseInteger;
728            }
729            catch (Exception ex)
730            {
731                throw new Exception("Entered bytesToUse is not an integer: " + ex.Message);
732            }
733
734            switch (((CostFunctionSettings)this.plugin.Settings).FunctionType)
735            {
736                case 0: //Index of coincidence
737                    return plugin.calculateIndexOfCoincidence(text, bytesToUse);
738                case 1: //Entropy
739                    return plugin.calculateEntropy(text, bytesToUse);
740                case 2: // Bigrams: log 2
741                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 2);
742                case 3: // Bigrams: Sinkov
743                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 3);
744                case 4: // Bigrams: Percentaged
745                    return plugin.calculateNGrams(plugin.ByteArrayToString(text), 2, 1);
746                case 5: // regular expression
747                    return plugin.regex(plugin.ByteArrayToString(text));
748                case 6:
749                    return plugin.calculateWeighted(plugin.ByteArrayToString(text));
750                default:
751                    throw new NotImplementedException("The value " + ((CostFunctionSettings)this.plugin.Settings).FunctionType + " is not implemented.");
752            }//end switch
753        }
754
755
756    #endregion
757    }
758
759}
760
Note: See TracBrowser for help on using the repository browser.